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方式都会引起额外的错误排序。所以可以得到如上的解法。
在不采用额外空间的限制下,我们可以利用中序遍历实时地检查错误。咋检查呢,我的妈。。。不知道怎么分析思路。。就先记住好了。。