A clean and fast dfs approach


  • 3
    Q
    class Solution {
        int balanceness(TreeNode *root) { // return depth if balanced, else -1
            if(!root) return 0;
            int ld=balanceness(root->left);
            if(ld>=0) {
                int rd=balanceness(root->right);
                if(rd>=0 && std::abs(ld-rd)<2) return 1+std::max(ld,rd);
            }
            return -1;
        }
    public:
        bool isBalanced(TreeNode* root) {
            return balanceness(root)>=0;
        }
    };

  • 0

    If ld is negative, then you should return without executing the left recursive call.


  • 0
    Q

    thanks, yes, it'd be better shortcircuited, edited accordingly.


Log in to reply
 

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