Recover Binary Search Tree.java

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
        TreeNode previous; 
    public void recoverTree(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<TreeNode> list=new ArrayList<TreeNode>();
        previous=null; 
        inOrder(root, list);
        int temp=list.get(0).val;
        list.get(0).val=list.get(list.size()-1).val; 
        list.get(list.size()-1).val=temp;
    }

    void inOrder(TreeNode root, ArrayList<TreeNode> list)
    {
        if(root==null) return ; 
        inOrder(root.left, list);
        if(previous!=null && previous.val>root.val)
        {
            if(!list.contains(previous)) list.add(previous);
            if(!list.contains(root)) list.add(root); 
        }
        previous=root; 
        inOrder( root.right, list);
    }
}