Recover Binary Search Tree

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

Recover the tree without changing its structure.


firstorder the value will increase, so we can find the first error

backorder the value will decrease, so we can find the second error.

change it 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode first;
    TreeNode second;
    private TreeNode pre;
    void inorder(TreeNode root){
        if(first != null) return;
        if(root == null) return;
        inorder(root.left);
        if(pre == null) pre=root;
        else{
            if(pre.val > root.val) {
                first = pre; return;
            }
            pre = root;
        }
        if(first == null)
            inorder(root.right);
    }
    void backorder(TreeNode root){
        if(second != null) return;
        if(root == null) return;
        backorder(root.right);
        if(pre == null) pre = root;
        else{
            if(pre.val < root.val) {
                second = pre;
                return;
            }
            pre = root;
        }
        if(second == null)
            backorder(root.left);
    }
   
    public void recoverTree(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        first = null;
        second = null;
       
        pre = null;
        inorder(root);
       
        pre = null;
        backorder(root);
       
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}