2020-10-28
Description:
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Example 2:
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
Solutions:
野路子Solution: 虽然解出来了，但是果然运行速度太慢了
NOTE: 先用dfs遍历二叉树，不断check每个node，标记出来有问题的node。如果搜索到底部，则保存当前move_hist到move_ls，当前correct_hist到corr_ls。 找出1-2个最特征的move_hist。如果是2个，则说明错误的两个node在某个parent的左右两边，否则说明在一条链上。
case1: 如果是左右两边则第两条move_hist第一个出问题的node的value互换。
case2: 如果是在一条链上，则需要利用move_hist构建在该链上的当前错误的排序，同时保存node和node.val到两个list，然后对node.val的list排序，最后把这些值赋给node的list。
一些测试集：
[20,35,30,5,15,25,10,3,7,13,17,23,27,33,37]
[30,10,20,5,15,25,35,3,7,13,17,23,27,33,37]
[27,10,30,5,15,25,35,3,7,13,17,23,20,33,37,null,null,null,null,null,null,null,null,null,null,26,28]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def check(node,mini,maxi):
if node == None:
return [True,True]
error = [None,None]
if node.left != None and (node.left.val > node.val or node.left.val < mini):
error[0] = False
else:
error[0] = True
if node.right != None and (node.right.val < node.val or node.right.val > maxi):
error[1] = False
else:
error[1] = True
return error
corr_ls = []
move_ls = []
def dfs(move_hist,correct_hist,node,mini,maxi):
left_corr,right_corr = check(node,mini,maxi)
if node.left != None:
if left_corr == False:
dfs(move_hist+"l",correct_hist+[left_corr],node.left,-math.inf,math.inf)
else:
dfs(move_hist+"l",correct_hist+[left_corr],node.left,mini,node.val)
if node.right != None:
if right_corr == False:
dfs(move_hist+"r",correct_hist+[right_corr],node.right,-math.inf,math.inf)
else:
dfs(move_hist+"r",correct_hist+[right_corr],node.right,node.val,maxi)
if node.left == None and node.right == None:
corr_ls.append(correct_hist)
move_ls.append(move_hist)
dfs("",[],root,-math.inf,math.inf)
problem_path = []
problem_corr = []
for i in range(len(corr_ls)-1,-1,-1):
if False not in corr_ls[I]:
continue
for j in range(len(corr_ls[i])-1,-1,-1):
if corr_ls[i][j] == False:
break
cache = move_ls[i][:j+1]
if not problem_path:
problem_path.append(cache)
problem_corr.append(corr_ls[I])
else:
if len(cache) > len(problem_path[-1]):
if problem_path[-1] == cache[:len(problem_path[-1])]:
problem_path[-1] = cache
problem_corr[-1] = corr_ls[I]
else:
problem_path.append(cache)
problem_corr.append(corr_ls[I])
elif problem_path[-1][:len(cache)] != cache:
problem_path.append(cache)
problem_corr.append(corr_ls[I])
# print(problem_path,"\n",problem_corr)
def navigate(path,corr):
cache = root
for i,s in enumerate(path):
if s == "l":
cache = cache.left
else:
cache = cache.right
if corr[i] == False:
break
return cache
def rearrange(path):
cache = root
value = [root.val]
node = [root]
last = 0
for s in path:
if s == "l":
cache = cache.left
node = node[:last] + [cache] + node[last:]
value = value[:last] + [cache.val] + value[last:]
else:
cache = cache.right
node = node[:last+1] + [cache] + node[last+1:]
value = value[:last+1] + [cache.val] + value[last+1:]
last += 1
# print(value)
value.sort()
# print(value)
for i in range(len(value)):
node[i].val = value[I]
if len(problem_path) == 2:
n1 = navigate(problem_path[0],problem_corr[0])
n2 = navigate(problem_path[1],problem_corr[1])
# print(n1.val,n2.val)
n1.val,n2.val = n2.val,n1.val
# print(n1.val,n2.val)
else:
rearrange(problem_path[0])
Runtime: 104 ms, faster than 5.23% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.7 MB, less than 5.78% of Python3 online submissions for Recover Binary Search Tree.
Solution2: O(n), inspired by https://www.cnblogs.com/grandyang/p/4298069.html 解法1
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def dfs(node):
if node.left == None and node.right == None:
return [node.val],[node]
val = []
nod = []
if node.left != None:
left_ret = dfs(node.left)
val += left_ret[0]
nod += left_ret[1]
val += [node.val]
nod += [node]
if node.right != None:
right_ret = dfs(node.right)
val += right_ret[0]
nod += right_ret[1]
return val,nod
value_ls,node_ls = dfs(root)
value_ls.sort()
for i,n in enumerate(node_ls):
n.val = value_ls[I]
Runtime: 76 ms, faster than 74.21% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.5 MB, less than 40.00% of Python3 online submissions for Recover Binary Search Tree.
Solution3: inorder traversal, O(n) space 不用递归
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
value = []
node = []
stack = []
curr = root
while curr != None or stack:
if curr != None:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
value.append(curr.val)
node.append(curr)
curr = curr.right
value.sort()
for i,n in enumerate(node):
n.val = value[I]
Runtime: 80 ms, faster than 53.35% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.5 MB, less than 40.00% of Python3 online submissions for Recover Binary Search Tree.
Solution4: Morris inorder traversal O(1) space
inspired by http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html and
https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
NOTE: 不用保存完整的traversal history，只需要保存last visited node（叫prev）就行了，这个last node初始化是None。然后凡是prev比curr大，就把这俩按顺序放到一个list里（叫problem）。两种情况：
不论那种情况，最终只需要把problem的开头和结尾的node的value互换就行了！
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
curr = root
prev = None
def FindPredecessor(node):
cache = node.left
while cache.right != None and cache.right != node:
cache = cache.right
return cache
problem = []
while curr != None:
if curr.left == None:
if prev != None and curr.val < prev.val: # 先比较
problem += [prev,curr] # 先比较
prev = curr # 先比较，之前这一步是ret.append(curr.val)
curr = curr.right
else:
pred = FindPredecessor(curr)
if pred.right == None:
pred.right = curr
curr = curr.left
else:
if prev != None and curr.val < prev.val: # 先比较
problem += [prev,curr] # 先比较
prev = curr # 先比较，之前这一步是ret.append(curr.val)
curr = curr.right
pred.right = None
p1,p2 = problem[0],problem[-1]
p1.val,p2.val = p2.val,p1.val
Runtime: 68 ms, faster than 95.79% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.3 MB, less than 90.00% of Python3 online submissions for Recover Binary Search Tree
