It is a DFS solution which only need reverse each node one time;


  • 0
    M
    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            return dfsheight(root) != -1;
        }
        int dfsheight(TreeNode* node) {
            if (node == NULL) return 0;
            int leftheight = dfsheight(node->left);
            int rightheight = dfsheight(node->right);
            if (leftheight == -1) return -1;
            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.