平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3

   / \

  9  20

    /  \

   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1

      / \

     2   2

    / \

   3   3

  / \

 4   4

返回 false 。

解法1 递归法 dfs(重复遍历结点多次)

public static boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int diff = left-right;
        if(diff >1 || diff<-1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public static int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return (left > right) ? (left+1) : (right+1);
    }
public static void main(String[] args) {
    TreeNode root = new TreeNode(3);
    TreeNode node1 = new TreeNode(9);
    TreeNode node2 = new TreeNode(20);
    TreeNode node3 = new TreeNode(15);
    TreeNode node4 = new TreeNode(7);
    root.left=node1;
    root.right=node2;
    node2.left=node3;
    node2.left=node4;
    System.out.println(isBalanced(root));
}
public static boolean isBalanced(TreeNode root) {
        height(root);
        return ans;
    }
static boolean ans = true;

public static int height(TreeNode root)
{
    if(root == null){
        return 0;
    }
    int left = height(root.left);
    int right = height(root.right);

    if(Math.abs(left-right) > 1){
        //这里可能是左子树大也可能是右子树大
        ans = false;
    }
    return 1 + Math.max(left,right);
}

解法2 （每个结点只遍历一次）

用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。

/**
 * 判断是否是平衡二叉树，第二种解法
 *
 * @param root
 * @return
 */
public static boolean isBalanced2(BinaryTreeNode root) {
    int[] depth = new int[1];
    return isBalancedHelper(root, depth);
}

public static boolean isBalancedHelper(BinaryTreeNode root, int[] depth) {
    if (root == null) {
        depth[0] = 0;
        return true;
    }

    int[] left = new int[1];
    int[] right = new int[1];

    if (isBalancedHelper(root.left, left) && isBalancedHelper(root.right, right)) {
        int diff = left[0] - right[0];
        if (diff >= -1 && diff <= 1) {
            depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);
            return true;
        }
    }

    return false;
}