C++ Typical O(N) solution by record states when DFS !


  • 0
    F
    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            return dfsHeight(root) != -1;
        }
        
        int dfsHeight(TreeNode* root) {
            if (root == nullptr)  return 0;
            int leftHeight = dfsHeight(root->left);
            if (leftHeight == -1) return -1;
            int rightHeight = dfsHeight(root->right);
            if (rightHeight == -1) return -1;
            if (abs(leftHeight - rightHeight) > 1)  return -1;
            return max(leftHeight, rightHeight) + 1;
        }
    };

Log in to reply
 

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