StraightForward, O(N) Function stack, C++ Solution


  • 0
    O

    The key is to keey a previous TreeNode,
    Since it's a BST, inorder traversal gives us a sorted order. Whenever we finish visiting a node, we update the prev TreeNode

    goLeft

    root, update(prev)

    goRight

    void recoverTree(TreeNode* root)
    {
        if(root == NULL)
            return;
        TreeNode* node1 = NULL, *node2 = NULL, *previous = NULL;
        
        traverse(root, parent, node1, node2);
        if(node1!=NULL && node2!=NULL)
        {
            int tmp = node1->val;
            node1->val = node2->val;
            node2->val = tmp;
        }
    }
    
    void traverse(TreeNode* root, TreeNode* & previous, TreeNode* & node1, TreeNode* & node2)
    {
        if(root == NULL)
            return;
            
        traverse(root->left, previous, node1, node2);
        int val = root->val;
        
        if(previous != NULL)
        {
            if( previous->val > root->val )
            {
                if(node1 == NULL)
                {
                    node1 = previous;
                    node2 = root;
                }
                else
                    node2 = root;
            }
        }
        previous = root;
        traverse(root->right, previous, node1, node2);
    }

Log in to reply
 

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