JZX轻语：简
LeetCode 971 - 翻转二叉树以匹配先序遍历
发表于2024年05月31日
树上递归有点费脑子的题目。大体思路是在这个棵树上进行先序遍历，然后尝试匹配当前子树的先序遍历序列，如果不匹配，那么就需要翻转当前子树的左右子树，然后再次进行匹配。匹配以递归的方式进行：如果当前子树的根节点和先序遍历序列的当前位置不匹配，那么就返回False，否则就递归匹配左右子树。如果左子树匹配失败，那么就尝试翻转当前子树的左右子树，然后再次递归匹配左子树；如果左子树匹配成功，那么就递归匹配右子树。最后返回匹配结果即可。
class Solution:
def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
ans = []
def dfs(cur_node: Optional[TreeNode], cur_pos: int) -> (bool, int):
# cur_pos是当前voyage的待匹配位置
# 返回值是当前子树是否匹配成功，以及匹配成功后的待匹配位置
# 该DFS既是树的先序遍历，也是匹配的过程，如果发生翻转操作，那么会在ans中记录
nonlocal ans
if cur_node is None:
return True, cur_pos
if cur_node.val != voyage[cur_pos]: # 当前子树的根节点和voyage不匹配, 不用继续了
return False, cur_pos
cur_pos += 1 # 匹配成功, 待匹配位置后移
# 先不翻转，尝试匹配左子树
left_ok, cur_pos = dfs(cur_node.left, cur_pos)
if not left_ok:
# 左子树匹配失败，尝试翻转左右子树再匹配
ans.append(cur_node.val)
right_ok, cur_pos = dfs(cur_node.right, cur_pos)
if not right_ok: # 翻转后还是匹配失败，返回False
return False, cur_pos
return dfs(cur_node.left, cur_pos)
else:
return dfs(cur_node.right, cur_pos)
ok, _ = dfs(root, 0)
if not ok:
return [-1]
return ans有一个点需要关注一下，由于树的每个节点的值都是唯一的，所以如果左子树在其非根节点下发生了不匹配，则右子树也不会匹配成功(因为左子树的根节点匹配成功了，由于没有重复的值，右子树势必在根节点处匹配失败)。
因此可以优化一下
class Solution:
def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
ans = []
def dfs(cur_node: Optional[TreeNode], cur_pos: int) -> (bool, int):
nonlocal ans
if cur_node is None:
return True, cur_pos
if cur_node.val != voyage[cur_pos]:
return False, cur_pos
next_pos = cur_pos + 1
left_ok, next_pos = dfs(cur_node.left, next_pos)
if not left_ok:
# 剪枝: 不匹配的位置在左子树的非根节点处，右子树不可能匹配成功
if next_pos != cur_pos + 1:
return False, next_pos
ans.append(cur_node.val)
right_ok, next_pos = dfs(cur_node.right, next_pos)
if not right_ok:
return False, next_pos
return dfs(cur_node.left, next_pos)
else:
return dfs(cur_node.right, next_pos)
ok, _ = dfs(root, 0)
if not ok:
return [-1]
return ans