Balanced Binary Tree

题目：

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.

分析：

其实这道题目和Maximum Depth of Binary Tree是通一道题目，只是在统计depth之外，判断一下left和right之差是否大于1。如果大于1，则说明不是平衡树了，干脆返回个不可能出现的-1。

在判断条件之前加上，如果我看到返回了-1，那子树已经不平衡了，我也不平衡好了。

解法：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    int maxDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }

        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        if (left == -1 || right == -1 || abs(left - right) > 1) {
            return -1;
        }
        return max(left, right) + 1;
    }

    bool isBalanced(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return true;
        }
        return maxDepth(root) != -1;
    }
};