LeetCode - 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?

Solution:

BST必需得考虑中序遍历。

我们用prev保存中序遍历时的前一个访问过的节点，first为交换的第一个节点，second为交换的第二个节点。

如果我们第一次碰到prev.val>node.val的情况，那么first=prev。

最后碰到prev.val>node.val的时候，second=node。

假如原BST为1,2,3,4,5,6,7

两个节点swap后为1,2,7,4,5,6,3

我们看到7>4，那么first节点为7。接下来4<5, 5<6都没问题。最后6>3，这时候second=3

然后交换7, 3两个节点的值。

private TreeNode prev, first, second;
public void recoverTree(TreeNode root) {
    if(root == null) return;
    inorder(root);
    int tmp = first.val;
    first.val = second.val;
    second.val = tmp;
}

public void inorder(TreeNode node) {
    if(node == null) return;
    inorder(node.left);
    if(prev != null && prev.val>node.val) {
        if(first == null) {
            first = prev;
        }
        second = node;
    }
    prev = node;
    inorder(node.right);
}