LeetCode 110 Balanced Binary Tree

LeetCode 110

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.

Diffculty
Easy

Similar Problems
[LeetCode 102] Binary Tree Level Order Traversal Medium

Analysis

如何判断二叉树是否 Balance ？

(1) 一个 binary tree 中有任何一个 subtree 不平衡，那么整个 tree 不平衡。 (2) 当 x->left 和 x->right 的 subtree 都平衡时，只有 左右子树高度相差小于等于1，也即 abs(depth(x->left) - depth(x->right)) <= 1 时，以 x 为根节点的子树才平衡。

只有当某一节点左右子树的 depth 以及左右子树是否平衡都得知以后，才能判断该节点为根的树是否平衡，以及求得该节点的 depth。 递归终止条件，遇到空节点 depth 返回 0 。

Solutions

解法一 用 depth 为 -1 来表示其子树不平衡

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if (root == nullptr) return true;
         return getHeight(root) == -1 ? false : true;
    }
    int getHeight(TreeNode *root) {
        if (root == nullptr) return 0;
        int left = getHeight(root->left);
        if(left == -1) return -1;              // no need to call right = getHeight(root->right) if left == -1
        int right = getHeight(root->right);
        if (right == -1) return -1;
        if (abs(left - right) > 1) return -1;  // 左右子树相差大于 1 时，说明不平衡，返回 -1 。e.g. 左子树返回 depth 为0，右子树返回 depth 为 2，显然就不平衡。
        return max(left, right) + 1;
    }
};

解法二 跟解法一几乎相同，只是更加简化

class Solution {
public:
    boolean isBalanced(TreeNode *root) {
        if(root == nullptr) return true;
        if(abs(depth(root->left) - depth(root->right)) > 1){ // 如果子树高度差大于 1 ，则不平衡
            return false;
        }
        return isBalanced(root->left) && isBalanced(root->right);
    }
    int depth(TreeNode *root){
        if(root == null) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
};