110. Balanced Binary Tree - cocoder39/coco39_LC GitHub Wiki

110. Balanced Binary Tree

Solution 1 (preferred): terminating bottom up dfs when finding out an unbalanced node. time complexity is O(n) and space complexity is O(h).

tip: use -1 to mark unbalanced node.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return depth(root) != -1;
    }
    
    int depth(TreeNode* root) {
        if (! root) {
            return 0;
        }
        
        int left = depth(root->left);
        if (left == -1) {
            return -1;
        }
        
        int right = depth(root->right);
        if (right == -1) {
            return -1;
        }
        
        return abs(left - right) <= 1 ? 1 + max(left, right) : -1;
    }
};

Solution 2: top down dfs is expensive as it would visit each node several times. time complexity t(n) = 2t(n/2) + O(n) = O(n * log n) when the sizes of two subtrees are equal.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (! root) {
            return true;
        }
        return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
    
    int depth(TreeNode* root) {
        if (! root) {
            return 0;
        }
        return 1 + max(depth(root->left), depth(root->right));
    }
};