Recover_Binary_Search_Tree.txt

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?
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void swap(TreeNode *p1, TreeNode *p2){
    	int temp;
		temp = p1->val;
		p1->val = p2->val;
		p2->val = temp;
	}

     
    /*check() find out the 2 elements in the tree;*/
	void check(TreeNode *root, TreeNode *&pre, TreeNode *&p1, TreeNode *&p2){
    if (root==NULL) return;
    check(root->left,pre,p1,p2);
    if (pre!=NULL&&root->val<pre->val)
	{//Note:need to verify pre!=NULL because they may not have value if it's NULL.
        if (p1==NULL) p1=pre;
			p2=root;    
    }
    pre=root;
    check(root->right,pre,p1,p2);
}

	void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TreeNode *p1=NULL, *p2=NULL, *pre=NULL;
    	check(root,pre,p1,p2);
		swap(p1,p2);
    }
};
REMARK:
1.IDEA: Don't try to swap 2 tree node, just swap the 2 values in the node.Then, how to find the 2 nodes? Use in-order traversal and record the current node and last visited node.