Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution:

这个解法是自顶向下的：从上往下 check 每个 node，但每次都要调用 getHeight，所以复杂度是 O(N^2). 这也是我自己的解法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) 
    {
        if(root == null)
            return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        if(Math.abs(leftHeight - rightHeight) > 1)
            return false;
        else
            return isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int getHeight(TreeNode root)
    {
        if(root == null)
            return 0;
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

看了 solution 发现一个自底向上的解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public boolean isBalanced(TreeNode root) 
    {
        int depth = getHeight(root);
        if(depth == -1)
            return false;
        return true;
    }
    
    public int getHeight(TreeNode root)
    {
        if(root == null)
            return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        if(leftHeight == -1) return -1;
        if(rightHeight == -1) return -1;
        
        if(Math.abs(leftHeight - rightHeight) > 1)
            return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

这个解法利用返回值，在 getHeight()中，在向上返回之前，顺便检查左右两边高度差，如果大于1则不平衡，返回-1，否则返回高度。这样在最顶上可以 check 时，如果返回值为-1，则整棵树非 balance。借助返回值来传递不平衡这个信息。