一、判断二叉树是否为平衡二叉树（时间复杂度O(N)）
平衡二叉树就是：要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过1。
解法：整个过程为二叉树的后序遍历。对任何一个节点node来说，先遍历node的左子树，遍历过程中收集两个信息，一个是node的左子树是否为平衡二叉树，一个是node的左子树最深到哪一层即为lH。如果发现node的左子树不是平衡二叉树，无须进行后续过程。如果node的左子树是平衡二叉树，在遍历node的右子树，同样收集两个信息。如果node的右子树也是平衡二叉树，就看lH和rH的绝对值是否大于1。如果大于1，就说明不是平衡二叉树。
注意：这里只能用boolean[] res而不能用boolean res做全局变量，如果boolean做全局变量会有问题。
public boolean isBalance(Node root) { boolean[] res = new boolean[1]; res[0] = true; getHeight(root, 1, res); return res[0]; } private int getHeight(Node root, int level, boolean[] res) { if (root == null) return level; int lH = getHeight(root.left, level + 1, res); if (!res[0]) return level; int rH = getHeight(root.right, level + 1, res); if (!res[0]) return level; if (Math.abs(lH - rH) > 1) res[0] = false; return Math.max(lH, rH); }
二、根据有序数组生成平衡搜索二叉树，并且该搜索二叉树的中序遍历的结果与有序数组一致
解法：用有序数组汇总最中间的数生成搜索二叉树的头节点，然后用这个数左边的数生成左子树，右边的数生成右子树即可。
public TreeNode sortedArrayToBST(int[] nums) { if (nums == null) return null; return generateNode(nums, 0, nums.length - 1); } private TreeNode generateNode(int[] nums, int start, int end) { if (start > end) return null; int mid = (start + end) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = generateNode(nums, start, mid - 1); root.right = generateNode(nums, mid + 1, end); return root; }
三、