99. Recover Binary Search Tree

Problem:

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

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Analysis:
From the example above we know that the first element is greater than its successor, the second element is smaller than its predecessor. We can find first and second swapped node easily with inorder traversal.

Solution:

class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        TreeNode prev = null;
        TreeNode first = null;
        TreeNode second = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (prev != null && prev.val >= cur.val && first  == null) {
                first = prev;
            }
            if (prev != null && prev.val >= cur.val && first != null) {
                second = cur;
            }
            prev = cur;
            cur = cur.right;
        }
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}