Recover Binary Search Tree
update Sep 1, 2017 21:52
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?
Basic Idea:
思路1( worst one, O(n) space, O(nlogn) time)：
O(n) space, O(nlogn) time)：虽然是一个比较简单的思路，但一开始我竟没有想出来。就是直接 inorder traverse，把node和val分别存入两个list，对val从小到大排序，然后依次对node list中的node赋值即可。
Python Code：
class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
def inorder(root):
if not root: return
inorder(root.left)
inorder_nodes.append(root)
inorder_vals.append(root.val)
inorder(root.right)
inorder_nodes = []
inorder_vals = []
inorder(root)
inorder_vals.sort()
for i in range(len(inorder_nodes)):
inorder_nodes[i].val = inorder_vals[i]思路2(O(1) space, O(n) time)：
O(1) space, O(n) time)：还是那句话，面对一道 hard 难度的题目，给出如上那么 “straight forward” 的解自然交不了差。要做到follow up的要求，我们需要知道一种叫做 Morris-Traversal 算法，这种算法可以实现 O(n) time and O(1) Space 的 Binary Tree Traversing；
这里 有个关于Morris-Traversal Alg 的介绍；
盗图一张： 
精髓就是每到一个节点，通过把它左子树中predecessor的右指针指向自己来实现向上的跟踪；
Python Code: 在实现的过程中，注意对不同的功能部分进行模块化，比如这里，我另外写了一个 visit(prev, node) 函数，这样可以让主要逻辑部分更加简洁易懂。
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
# 找到左子树中最大的，也就是当前node的predecessor
def getPred(node):
temp = node.left
while temp and temp.right:
if temp.right is node: # 说明pred.right == curr, 返回null，并恢复pred.right
temp.right = None
return None
temp = temp.right
return temp
# visit given node, find two swiched nodes
def visit(prev, node):
if prev and prev.val > node.val:
print(str(prev.val) + " " + str(node.val))
if self.first is None:
self.first = prev
self.second = node # 这里是为了解决tree中只有两个node的情况
else:
self.second = node
# morris inorder traversal, find target nodes along the way
self.first, self.second = None, None
prev = None
curr = root
while curr:
pred = getPred(curr)
# 这里包括了如下情况：
# curr.left == null (此时pred为null)
# curr 的 pred.right == curr，说明左边已经都visited，getPred（）会恢复pred.right为null，并返回null
# 我们要做的都是visit curr，然后让curr右移
if not pred:
visit(prev, curr)
prev = curr
curr = curr.right
# 剩下的情况就是pred.right == None，此时令其指向curr，然后curr左移
else:
pred.right = curr
curr = curr.left
t = self.first.val
self.first.val = self.second.val
self.second.val = tJava Code:
class Solution {
private TreeNode FIRST;
private TreeNode SECOND;
public void recoverTree(TreeNode root) {
TreeNode curr = root;
TreeNode prev = null;
while (curr != null) {
TreeNode pred = getPred(curr);
if (pred == null) {
visit(prev, curr);
prev = curr;
curr = curr.right;
} else {
pred.right = curr;
curr = curr.left;
}
}
int temp = FIRST.val;
FIRST.val = SECOND.val;
SECOND.val = temp;
}
private void visit(TreeNode prev, TreeNode node) {
if (prev != null && prev.val > node.val) {
if (FIRST == null) {
FIRST = prev;
SECOND = node;
} else {
SECOND = node;
}
}
}
private TreeNode getPred(TreeNode node) {
TreeNode temp = node.left;
while (temp != null && temp.right != null) {
if (temp.right == node) {
temp.right = null;
return null;
}
temp = temp.right;
}
return temp;
}
}Note
关于在便利过程中找first和second的方法，灵感来自 这里; 关键步骤：
Inorder traverse, keep the previous tree node, Find first misplaced node by
if ( current.val < prev.val ) Node first = prev;Find second by
if ( current.val < prev.val ) Node second = current;After traversal, swap the values of first and second node. Only need two pointers, prev and current node. O(1) space.
该方法时间复杂度分析:
因为 Morris Traversal 的过程中我们最多见到每个 node 3 次，所以总的时间复杂度仍然为 O(n);
思路3 (fastest, O(n) time/space)
这种思路最简单，就是直接 inorder 整个树，用方法2中的方法记录fist和second，然后互换值。
class Solution {
private TreeNode first, second, prev;
public void recoverTree(TreeNode root) {
inorder(root);
int t = first.val;
first.val = second.val;
second.val = t;
}
private void inorder(TreeNode curr) {
if (curr == null) return;
inorder(curr.left);
if (prev != null && prev.val > curr.val) {
if (first == null) {
first = prev;
second = curr;
} else {
second = curr;
}
}
prev = curr;
inorder(curr.right);
}
}update 2018-06-10 15:36:20
Update C++ Solution
增加一种 O(n) 时间，O(logN) 空间的解法，直接inorder遍历，维持一个全局变量prev，和全局变量first and second，其他部分和之前的方法类似，在inorder traversal 的过程中更新 first 和 second，最后 swap。
class Solution {
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = nullptr;
void inorder(TreeNode* curr) {
if (curr == nullptr) return;
inorder(curr->left);
if (prev && prev->val > curr->val) {
if (! first) {
first = prev;
second = curr;
} else second = curr;
}
prev = curr;
inorder(curr->right);
}
public:
void recoverTree(TreeNode* root) {
inorder(root);
int t = first->val;
first->val = second->val;
second->val = t;
}
};