给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
解题思路
理解最大直径=左子树最大高度+右子树的最大高度。就转化为求子树的最大高度，就可以用递归处理了。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
process(root);
return maxDiameter;
}
public int process(TreeNode node) {
if (node == null)
return 0;
int leftHeight = process(node.left);
int rightHeight = process(node.right);
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1;
}
}
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。
解题思路：
如何保持平衡：通过选取列表中间的数，作为根节点。继续递归执行。
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0)
return null;
return buildBST(nums, 0, nums.length - 1);
}
public TreeNode buildBST(int[] nums, int left, int right) {
if (left > right)
return null;
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildBST(nums,left,mid-1);
root.right = buildBST(nums,mid+1,right);
return root;
}
}
解题思路
- 因为给的树本身就是二叉搜索树，只需要按照左根右遍历，就可以得到升序的结果。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int[] nums = new int[10000];
int i = 0;
public int kthSmallest(TreeNode root, int k) {
if (root == null) return -1;
process(root);
return nums[k-1];
}
private void process(TreeNode root) {
// 左 根 右
if (root == null) return;
if (root.left!=null)
process(root.left);
nums[i++] = root.val;
if (root.right!=null)
process(root.right);
}
}
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
// System.out.println("处理节点: " + root.val);
TreeNode rightTemp = root.right;
root.right = root.left;
root.left = null;
TreeNode curr = root;
while (curr.right != null) {
curr = curr.right;
}
curr.right = rightTemp;
// 递归处理右子树，这会处理所有节点
flatten(root.right);
}
}
