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: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution

class Solution {
public:
    TreeNode *first = NULL, *second = NULL;
    TreeNode *prev = new TreeNode(INT_MIN);
    void inorder(TreeNode* root) {
        if ( root == NULL ) return;
        inorder(root->left);
        if ( root->val < prev->val ) {
            if ( first == NULL ) first = prev;
            second = root;
        }
        prev = root;
        inorder(root->right);
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
        return;
    }
};

Notes

• 需要利用额外空间的解法非常简单，利用中序遍历的结果，找到位置错误的两个index就好了。其实找这个index也非常tricky。最笨的办法就是把结果sort一遍，然后看哪两个值不对。但其实有更neat的解法：

  def findPair(nums):
  n = len(nums)
  wrong1, wrong2 = -1, -1
  for i in range(1, n, 1):
    if ( nums[i] >= nums[i-1] ): continue
    if ( wrong1 == -1 ):
      wrong1 = i-1
    wrong2 = i
  return [wrong1, wrong2]
  

  这里如果发现一对顺序有误的相邻的pair （i-1和i），

  • 如果是第一次发现错误，那么就记下这两个index；
  • 如果不是第一次了，那么我们就需要仔细考虑一下下面这种情形： ...nums[wrong1] > nums[wrong2] < .... < nums[i-1] > nums[i]
    错误肯定在这四个index中，而且已知只有两个index错误，并且一个是wrong1或者wrong2，一个是i-1或者i。遍历一下交换两个index之后的结果可以发现，只能交换 wrong1和i，其他的switch方式都会引起额外的错误排序。所以可以得到如上的解法。

• 在不采用额外空间的限制下，我们可以利用中序遍历实时地检查错误。咋检查呢，我的妈。。。不知道怎么分析思路。。就先记住好了。。