C++ O(n) with no extra tree traversal for height measuring

  • 0

    The idea is, rather than measuring the height on each tree, we calculating current height on each node using just a simple DFS. Set balanced flag to false if you see unbalance heights of left and right children, and stop processing other parts as quickly as possible.

        bool isBalanced(TreeNode* root) {
            bool balanced = true;
            dfs(root, balanced);
            return balanced;
        int dfs(TreeNode* root, bool& balanced) {
            if (!root || !balanced) return 0;
            int ld = dfs(root->left, balanced);
            int rd = dfs(root->right, balanced);
            if (abs(ld - rd) > 1) balanced = false;
            return max(ld, rd)+1;

Log in to reply

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