99. Recover Binary Search Tree

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

Recover the tree without changing its structure.

Note:

Please make sure spalce complexity is O(1);

Analysis:

Do a in order traversal. should be ascending order but 2 element are weird because of the swap.

What weird? previous.val > root.val.

Create an Arraylist. First time we see prev.val>root.val, we add prev to arraylist since its for sure one of the 2 weird node we want. Whenever prev.val>root.val happens, store root at a variable "weird". Since we dont want to miss weird when 2 weird are adjacent but we only store prev. After traversal, add "weird" into array list. Swap value of 2 elements in arraylist.

Complexity:

Time: O(N)

Space: O(1)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev, weird;
    List<TreeNode> toSwapList;
    public void recoverTree(TreeNode root) {
        if(root == null)
        {
            return;
        }
        toSwapList = new ArrayList<TreeNode>();
        inTra(root);
        toSwapList.add(weird);
        int temp = toSwapList.get(0).val;
        toSwapList.get(0).val = toSwapList.get(1).val;
        toSwapList.get(1).val = temp;
    }

    private void inTra(TreeNode root)
    {
        if(root == null || toSwapList.size() == 2)
        {
            return;
        }
        inTra(root.left);
        if(prev != null)
        {
            if(prev.val > root.val)
            {
                if(toSwapList.isEmpty()){
                    toSwapList.add(prev);
                }
                weird = root;
            }
        }
        prev = root;
        inTra(root.right);
    }
}