99. Recover Binary Search Tree

Leetcode Tree Depth-first Search

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

Follow up:

• A solution using $O(n)$ space is pretty straight forward.
• Could you devise a constant space solution?

分析

这道题目其实一点都不难，最多medium，就是中序遍历的升级版。难点是确定发生错误的节点。因为交换错误非常简单，把两个节点值互换而已。那么怎么确定发生错误的节点呢？我们知道搜索二叉树的中序遍历是升序序列，发生交换有两种情况：

• 两个相邻节点互换，有1个数字不遵循升序序列

   3       
  / \   
 /   \  
 1   4   
    /   
    2             
中序遍历：[1,3,2,4]
   2       
  / \   
 /   \  
 1   4   
    /   
    3              
中序遍历：[1,2,3,4]

• 两个不相邻节点互换，有2个数字不遵循升序序列。

   2       
  / \   
 /   \  
 4   1   
    /   
    3             
中序遍历：[4,2,3,1]
   2       
  / \   
 /   \  
 1   4   
    /   
    3          
中序遍历：[1,2,3,4]

第二种情况则很简单，直接交换；那么第一种呢，观察发现，当两个相邻节点互换，两个节点在遍历的时候分别为发现错误的节点和错误节点的前一个节点。

private TreeNode prev;   // 前一个节点的值
private int num = 0;   // 遍历的节点个数
private TreeNode errorNode1, errorNode2;   // 错误的节点 
public void recoverTree(TreeNode root) {
    errorNode1 = null;
    errorNode2 = null;
    num = 0;
    inorderTraversal(root);
    int temp = errorNode2.val;
    errorNode2.val = errorNode1.val;
    errorNode1.val = temp;
}

private void inorderTraversal(TreeNode root) {
    if (root == null) return;
    inorderTraversal(root.left);
    if (num++ != 0 && root.val <= prev.val) {
        if (errorNode2 == null)
            errorNode1 = prev;
        errorNode2 = root;
    }
    prev = root;
    inorderTraversal(root.right);
}