recovery binary search tree.txt

class Solution {
     TreeNode firstNode;
        TreeNode secondNode;
        TreeNode preNode;
        TreeNode temp;
    public void recoverTree(TreeNode root) {
       backtrace(root);
        int num=firstNode.val;
        firstNode.val=secondNode.val;
        secondNode.val=num;
    }
    void backtrace(TreeNode root)
    {
        if(root==null)
            return;
        backtrace(root.left);
        if (preNode == null || preNode.val<= root.val) preNode = root; //update the preNode
    else //we found the wrong node
    {
        if (firstNode== null) firstNode = preNode;                 
        secondNode = root; 
    }
    backtrace(root.right);
    }
}