难度: Hard
原题连接
内容描述
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?
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
先来个inorder然后再来一遍遍历看看哪两个node不符合inorder的顺序，再来一遍遍历swap这两个node就可以
beats 45.45%
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.res = []
def inorder(root):
if not root:
return []
inorder(root.left)
self.res.append(root.val)
inorder(root.right)
return self.res
nodes = inorder(root) # get real order of binary tree
sorted_nodes = sorted(nodes) # get correct order of inary tree
diff = []
for i in range(len(nodes)): # get those two mistake node
if nodes[i] != sorted_nodes[i]:
diff.append(nodes[i])
def traverseAndSwap(root): # traverse and swap those two ndoes
if not root:
return
traverseAndSwap(root.left)
if root.val == diff[0]:
root.val = diff[1]
elif root.val == diff[1]:
root.val = diff[0]
traverseAndSwap(root.right)
traverseAndSwap(root)思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
其实不用遍历两次，一次就够了，参考qwl5004
beats 78.73%
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.first_node = TreeNode(None)
self.second_node = TreeNode(None)
self.prev_node = TreeNode(-sys.maxsize-1)
self.traverse(root)
self.first_node.val, self.second_node.val = self.second_node.val, self.first_node.val
def traverse(self, root):
if not root:
return
self.traverse(root.left)
if self.prev_node.val > root.val:
if not self.first_node.val: # 第一个点还没找到
self.first_node = self.prev_node # 第一个点肯定是因为大于后面的点才不符合，因此第一个点取prev_node
# 每次我们都更新second是因为我们要考虑corner case that two incorrect nodes are in same pair
self.second_node = root # 第二个点肯定是因为小于前面的点才不符合，因此第二个点取root
self.prev_node = root
self.traverse(root.right)当满足if self.prev_node.val > root.val:的时候，里面的逻辑我们可以写的更加sb一些，但是更清晰，
因为如果第一个点已经找到了，那么我们就已经给first_node assign了值了，后面的if self.first_node.val自然就满足了，但是这样就不用每一次都更新second_node了，因为我们只有在第一个点找到之后才会关注第二个点，即使在corner case中two incorrect nodes are in same pair，这两个点在inorder顺序中相邻，提前开始update second_node也是无用功，但是省不了时间，因为我们每次也要check一下if self.first_node.val and self.prev_node.val >= root.val:
if not self.first_node.val and self.prev_node.val >= root.val: # 第一个点还没找到
self.first_node = self.prev_node # 第一个点肯定是因为大于后面的点才不符合，因此第一个点取prev_node
if self.first_node.val and self.prev_node.val >= root.val: # 第一个点找到了
self.second_node = root # 第二个点肯定是因为小于前面的点才不符合，因此第二个点取root
思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******
迭代
beats 95.10%
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
first, second, prev = None, None, None
stack = []
cur = root
while stack or cur:
if cur: # visit curr's left subtree
stack.append(cur)
cur = cur.left
else: # done left subtree of curr Node
cur = stack.pop()
# compare curr.val with prev.val if we have one
if prev and cur.val < prev.val:
if not first: # incorrect smaller node is always found as prev node
first = prev
second = cur # incorrect larger node is always found as curr node
# visit curr's right subtree
prev = cur
cur = cur.right
first.val, second.val = second.val, first.val # recover swapped nodes思路 4 - 时间复杂度: O(N)- 空间复杂度: O(1)******
Morris traversal, 每次都用pred记录下当前访问点cur的左子树中right-most的那个点，将pred与cur连接起来 访问完cur的左子树之后，我们要利用pred回到cur，继而继续访问cur的右子树
这样可以不需要递归的栈调用，也不需要迭代的stack，空间可以省到O(1)
beats 99.32%
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
first, second, prev = None, None, None
pred = None # rightmost node in left tree
cur = root
while cur:
# for each node, we compare it with prev node as we did in in-order-traversal
if prev and cur.val < prev.val:
if not first:
first = prev
# we may have corner case that two incorrect nodes are in same pair.
# so we assign second with a new node at each time
second = cur
if cur.left: # got left tree, then let's locate its rightmost node in left tree
pred = cur.left
# we may have visited the left tree before,
# and connect the rightmost node with curr node (root node)
while pred.right and pred.right != cur:
pred = pred.right
if pred.right == cur: # this condition happens if and only if we have visited left tree before
# if this left tree has been visited before, then we are done with it
# cut the connection with currNode and start visit curr's right tree
pred.right = None
prev = cur
cur = cur.right
else:
# if this left tree has not been visited before,
# then we create a back edge from rightmost node to curr node,
# so we can return to the start point after done the left tree
pred.right = cur
cur = cur.left
else: # no left tree, then just visit its right tree
prev = cur
cur = cur.right
first.val, second.val = second.val, first.val