O(n) C++ solution


  • 0
    Y

    In the computing process for computing the height of the root, we actually compute the heights for the nodes. So we don't have to repeat this process for the left and right subtree. The idea for an O(n) solution is to add a flag, and dynamically check if the left, right depths are different by 1. Once you get a node with left, right depths are more than 1, set the flag, then skip the recursion for computing the depth for root.

    private:
             bool Balanced;
    public:
    bool isBalanced(TreeNode* root) {
            Balanced=true;
            maxDepth(root);
            return Balanced;
        }
        
        int maxDepth(TreeNode *root){
            if (!Balanced) return -1;
            if (!root) return 0;
            int l=maxDepth(root->left), r=maxDepth(root->right);
            if (l>r+1 || r>l+1) {
                Balanced=false; 
                return -1;
            }
            else return max(l,r)+1;
        }

Log in to reply
 

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