[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.

Analysis:

For BST, the inorder traversal will get the list of elements in sorted order. If two elements were swapped, there are two cases, the elements are next to each other or not. 

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

Doing an inorder traversal and the elements are marked as p1 and p2 if current element is less than previous element.   

class Solution {
public:

    void helper(TreeNode *root, TreeNode* &prev, TreeNode* &p1, TreeNode* &p2) {
        if (root == NULL)
            return;
        
        helper(root->left, prev, p1, p2);
            
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL)
            {
                p1 = prev;
                p2 = root;
            }
            else
            {
                p2 = root;
            }
        }
        
        prev = root;
        
        helper(root->right, prev, p1, p2);
    }

    void recoverTree(TreeNode *root) {
        TreeNode *prev = NULL;
        TreeNode *p1 = NULL;
        TreeNode *p2 = NULL;
        
        helper(root, prev, p1, p2);
        
        swap(p1->val, p2->val);
    }
};