Recover Binary Search Tree

Not a difficult question. The basic idea is to use a queue as a cache to store 2 successive nodes to find the pair where the first one is larger than second one in preorder traversal of this tree. Find 2 pairs like that, or only 1 pair might be found, then swap the values of appropriate nodes. Since res1, res2, and queue are all of size 3, I believe it should meet the constant space requirement.  


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) return;
       
        ArrayList<TreeNode> res1 = new ArrayList<TreeNode>();
        ArrayList<TreeNode> res2 = new ArrayList<TreeNode>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        findOneLargerThanNext(root,queue,null,res1);
        queue.clear();
        findOneLargerThanNext(root,queue,res1,res2);
       
        if(!res1.isEmpty() && !res2.isEmpty()){
            int tmp = res1.get(0).val;
            res1.get(0).val = res2.get(1).val;
            res2.get(1).val = tmp;
        }
        else{
            if(res2.isEmpty()){//swap result in res1
                int tmp = res1.get(0).val;
                res1.get(0).val = res1.get(1).val;
                res1.get(1).val = tmp;               
            }
        }
    }
   
    public void findOneLargerThanNext(TreeNode root,LinkedList<TreeNode> queue,ArrayList<TreeNode> res1,ArrayList<TreeNode> res2){
        if(root == null || res2.size() == 2){
            return;
        }
        findOneLargerThanNext(root.left,queue,res1,res2);
        if(queue.size() == 2){
            queue.remove(0);
        }
        queue.add(root);
        if(queue.size() == 2){
            if( (res1 == null || !res1.containsAll(queue))// res1 is NOT as same as res2
                    && res2.isEmpty() && queue.get(0).val > queue.get(1).val){
                res2.addAll(queue);
                return;
            }
        }
        findOneLargerThanNext(root.right,queue,res1,res2);       
    }
}