9ms iterative C++ solution


  • 0
    S

    First I'd like to present my 16ms recursive solution:

    {
        if (!root) {
            height=0;
            return true;
        }
        int left, right;
        bool ans= (isBalanced(root->left, left)&&isBalanced(root->right, right)&&(left-right>0?left-right:right-left)<=1);
        height=1+max(right, left);
        printf("val=%d left=%d right=%d\n", root->val, left, right);
        return ans;
    }
    bool isBalanced(TreeNode* root) {
        int height;
        return isBalanced(root, height);
    }
    
    I won't bother explain it as it is quite straight foward, then I convert it to an iterative solution using stack, and the time comes down to 
    9ms:
    
    
    ```struct Frame{
        int left, right;
        int & height;
        TreeNode* root;
        unsigned char status;
        Frame(TreeNode* root, int & height):root(root),height(height),status(0){}
    };
    bool isBalanced(TreeNode* root) {
        stack<Frame> s;
        int height;
        bool ret=true;
        s.push(Frame(root, height));
        while (s.size()) {
            Frame & f=s.top();
            //if (f.root) {
            //    printf("entering frame %d.\n", f.root->val);
            //}
            if (!f.status) {
                if (!f.root) {
                    f.height=0;
                    ret=true;
                    s.pop();
                    continue;
                }
                f.status=1;
                s.push(Frame(f.root->left, f.left));
            }
            else if (f.status==1) {
                if (!ret) {
                    break;
                }
                f.status=2;
                s.push(Frame(f.root->right, f.right));
            }
            else {
                if (!ret||(f.left-f.right>0?f.left-f.right:f.right-f.left)>1) {
                    ret=false;
                    break;
                }
                f.height=1+max(f.right, f.left);
                ret=true;
                s.pop();
            }
        }
        return ret;
    }
    
    As you can see the main performance gain in iterative solution is once it reached an unbalanced subtree it can immediately jumps out of the entire iteration and return!

Log in to reply
 

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