发表于 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

• LC 题目链接