! ? Leetcode - Recover Binary Search Tree

Recover Binary Search Tree

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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev;
    
    public void recoverTree(TreeNode root) {
        if(root == null)    return;
        
        ArrayList<TreeNode> wrongList = new ArrayList<TreeNode>();
        prev = null;
        inOrder(root, wrongList);
        
        int tmp = wrongList.get(0).val;
        wrongList.get(0).val = wrongList.get(wrongList.size() - 1).val;
        wrongList.get(wrongList.size() - 1).val = tmp;

    }
    
    public void inOrder(TreeNode node, ArrayList<TreeNode> wrongList) {
        if(node == null)    return;
        
        inOrder(node.left, wrongList);
        
        // if found
        if(prev != null && prev.val > node.val) {
            if(!(wrongList.contains(prev))) wrongList.add(prev);
            if(!(wrongList.contains(node))) wrongList.add(node);
        }
        prev = node;
        
        inOrder(node.right, wrongList);
    }
}

Reference:
1. http://jane4532.blogspot.com/2013/07/recover-binary-search-treeleetcode.html
2. https://gist.github.com/guolinaileen/5125340