971_翻转二叉树以匹配先序遍历

类型：树

• 971. 翻转二叉树以匹配先序遍历 💛 ⭐

  https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal/

  ❓ 给你一棵含有 n 个结点的二叉树，每个结点的值不同，且处于 1 - n 的范围。在给你一个数组 voyage 表示想要得到的前序遍历结果。交换一个结点的左右子树称为对该结点进行的一次交换操作。请你用最少的交换次数使得二叉树的前序遍历结果与 voyage 一致。可以完成的话，返回执行交换操作的结点的列表，否则返回 [-1]。

  💡 DFS

  进行深度优先遍历，如果我们即将遍历的结点的值与下一个期望数字 voyage[i] 不相同时，我们就要翻转一下当前这个结点。然后继续往下走。如果往下走之后仍然发现当前结点的值不等于 voyage[i] 那么就只能返回 [-1] 了。

  class Solution(object):
      def flipMatchVoyage(self, root, voyage):
          self.flipped = []
          self.i = 0
  
          def dfs(node):
              if node:
                  if node.val != voyage[self.i]:
                      self.flipped = [-1]
                      return
                  self.i += 1
  
                  if (self.i < len(voyage) and
                          node.left and node.left.val != voyage[self.i]):
                      self.flipped.append(node.val)
                      dfs(node.right)
                      dfs(node.left)
                  else:
                      dfs(node.left)
                      dfs(node.right)
  
          dfs(root)
          if self.flipped and self.flipped[0] == -1:
              self.flipped = [-1]
          return self.flipped

  时间复杂度：O(n)，空间复杂度：O(n)