[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Pasted from <http://leetcode.com/onlinejudge>

Analysis:

If we can use O(n) space , it is straight forward to get the  solution: do an in-order travel and put the node in the array; iterate the array and you will find the two which are not in ascending order.

But do we really need O(n) space?  Basically, if we can get the node p1 and p2, then swapping the value of p1 and p2 would recover the tree.  We don't have to remember all other nodes.  So when we do an in-order travel and compare the current node value with the previous node value, if we can find a node which has a value less than the previously visited node, either the current node or the previous node are the node swapped by mistake. There are two scenario to be considered: the node swapped are neighbors or not neighbors.

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

The code simply express themselves. 

Note, iterative in-order travel does not work for this questions since it use O(n) space for the stack.  

void recoverTreeHelper(TreeNode *root, TreeNode*& prev, TreeNode* &p1, TreeNode* &p2) {

    if (root != NULL)
    {
        recoverTreeHelper(root->left, prev, p1, p2);
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL) {
                p1 = prev;
                p2 = root;
            }
            else
                p2 = root;
        }
        else
            prev = root;

        recoverTreeHelper(root->right, prev, p1, p2);
    }
}

void recoverTree(TreeNode *root) {

    TreeNode* p1 = NULL;
    TreeNode* p2 = NULL;
    TreeNode* prev = NULL;

    recoverTreeHelper(root, prev, p1, p2);

    if (p1 != NULL && p2 != NULL)
        swap(p1->val, p2->val);
}