Loop Binary Tree Solution - Recover Binary Search Tree

1. Processing queue is O(1) solution
2. The easy only way is to find the order of the BST which is to simulate the In Order traversal… this needs to be very sure so that come up with this solution.
3. Find first element (pre node), then set the second to be the one after this one… it is possible that sec - first == 1; Continue looping and if find a second, the reset the second… Swap first and second…
4. Set a pre node before the current one, update it…if cur is the first node, then pre is null...

/**
 * 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> inorder = new ArrayList<TreeNode>();
        // ArrayList<Integer> inorderInts = new ArrayList<Integer>();
        TreeNode firstOne = null;
        TreeNode secondOne = null;
        TreeNode cur = root;
        TreeNode pre = null;
        Stack<TreeNode> process = new Stack<TreeNode>();
        while(cur != null || !process.isEmpty()){
            if(cur != null){
                process.push(cur);
                cur = cur.left;
            }else{
                cur = process.pop();
                if(pre != null){
                    if(cur.val < pre.val){
                        if(firstOne == null){
                            firstOne = pre;
                        }
                        secondOne = cur;//Tricky: replace by the second qualified element
                    }
                }
                pre = cur;
                // inorder.add(cur);
                // inorderInts.add(cur.val);
                cur = cur.right;
            }
        }
        if(firstOne != null && secondOne != null){
            int temp = firstOne.val;
            firstOne.val = secondOne.val;
            secondOne.val = temp;
        }
        // if(inorder.size() < 2){
        //     return;
        // }
        // Collections.sort(inorderInts);
        // for(int i = 0; i < inorder.size(); i++){
        //     inorder.get(i).val = inorderInts.get(i);
        // }
    }
}