C++ O(N) dfs, 9 lines


  • 2
    N

    pair<int, bool> stands for current tree's depth and is balanced.

    class Solution {
        pair<int, bool> dfs(TreeNode *x) {
            if (!x) return { 0, true };
            auto l = dfs(x->left);
            auto r = dfs(x->right);
            return { max(l.first, r.first) + 1, l.second && r.second && abs(l.first - r.first) <= 1 };
        }
    public:
        bool isBalanced(TreeNode* root) {
            return (dfs(root)).second;
        }
    };
    

  • 0
    C

    Really elegant and efficient solution! Thank you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.