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.

http://www.lintcode.com/en/problem/balanced-binary-tree/

Discussion

要保证左子树和右子树的maximum depth相差不超过1， 并且左右子树都是Blanced Binary Tree。

Solution

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    bool isBalanced(TreeNode *root) {
        // write your code here
        if(root == nullptr) return true;

        return abs(maxLen(root->left) - maxLen(root->right)) <= 1
            && isBalanced(root->right) && isBalanced(root->left);
    }
private:
    int maxLen(TreeNode *root) {
        if(root == nullptr) return 0;
        return max(maxLen(root->left), maxLen(root->right)) + 1;
    }
};