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

标签: 树 深度优先搜索 二叉树

难度: Medium

给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。

另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。

通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：

请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。 

如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。

 

示例 1：

输入：root = [1,2], voyage = [2,1]
输出：[-1]
解释：翻转节点无法令先序遍历匹配预期行程。

示例 2：

输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。

示例 3：

输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
解释：先序遍历已经匹配预期行程，所以不需要翻转节点。

 

提示：

  • 树中的节点数目为 n
  • n == voyage.length
  • 1 <= n <= 100
  • 1 <= Node.val, voyage[i] <= n
  • 树中的所有值 互不相同
  • voyage 中的所有值 互不相同

Submission

运行时间: 25 ms

内存: 16.1 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        def dfs(node, index, flipped, result):
            if not node:
                return index

            if node.val != voyage[index]:
                return -1

            index += 1

            if index < len(voyage) and node.left and node.left.val != voyage[index]:
                if not node.right or node.right.val != voyage[index]:
                    return -1

                # Flip the node
                node.left, node.right = node.right, node.left
                flipped.append(node.val)

            index = dfs(node.left, index, flipped, result)
            if index == -1:
                return -1

            index = dfs(node.right, index, flipped, result)
            if index == -1:
                return -1

            return index

        flipped = []
        result = []

        if dfs(root, 0, flipped, result) != len(voyage):
            return [-1]

        return result if not flipped else flipped

Explain

这个解题思路是通过深度优先搜索（DFS）来比较树的当前先序遍历结果与给定的voyage序列。从根节点开始，每次访问一个节点时，都检查它是否与voyage中相应位置的值匹配。如果当前节点的左子节点存在且其值与voyage中下一个值不匹配，则检查右子节点是否与voyage中的这个值匹配。如果匹配，则交换左右子节点（即翻转当前节点），并记录这次翻转。之后，继续对左右子节点递归进行DFS。如果在任何时候节点值与voyage不匹配，且无法通过翻转来匹配，就返回-1表示无法匹配。最后，如果整个树都能与voyage匹配，则返回记录的翻转节点列表，否则返回[-1]表示无法匹配。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:
        def dfs(node, index, flipped, result):
            if not node:
                return index

            if node.val != voyage[index]:
                return -1

            index += 1

            if index < len(voyage) and node.left and node.left.val != voyage[index]:
                if not node.right or node.right.val != voyage[index]:
                    return -1

                # Flip the node
                node.left, node.right = node.right, node.left
                flipped.append(node.val)

            index = dfs(node.left, index, flipped, result)
            if index == -1:
                return -1

            index = dfs(node.right, index, flipped, result)
            if index == -1:
                return -1

            return index

        flipped = []
        result = []

        if dfs(root, 0, flipped, result) != len(voyage):
            return [-1]

        return result if not flipped else flipped

Explore

在先序遍历中，节点值不匹配时首先尝试翻转节点是为了尝试使当前节点的子节点顺序与voyage序列中的顺序一致，从而继续先序遍历。这种翻转操作确实有可能导致后续的遍历序列完全不匹配，这通常发生在翻转之后的树结构与voyage的结构本质上不兼容的情况下。如果翻转后序列仍然不能匹配，算法会检测到这一点并最终返回-1，表示无法通过翻转来匹配全部序列。

在DFS递归中，索引`index`用于跟踪当前访问的节点在voyage序列中的位置。每次递归调用处理一个节点后，`index`增加1。当递归调用左子节点或右子节点时，将更新后的`index`传递给子调用。递归函数返回时，返回的是处理完所有子节点后的最新`index`。这样确保每层递归都使用正确的索引，并且所有修改都基于最新的遍历进度，从而在整个DFS过程中保持`index`的准确性。

在算法中，如果某个节点需要翻转来匹配voyage序列，但该节点只有一个子节点（无论是左是右），则不执行翻转操作，因为翻转单个子节点没有意义。此时，如果该单一子节点不匹配voyage中对应的值，将返回-1，表示无法匹配。这种情况下，算法会检测这种不匹配并直接处理，而不尝试无效的翻转。

当翻转操作发生后，原来的左子节点和右子节点的位置被交换。在继续DFS递归遍历时，会首先遍历新的左子节点（原右子节点），然后遍历新的右子节点（原左子节点）。这种处理方式确保了在翻转之后，节点的遍历顺序符合先序遍历的要求，并与更新后的voyage序列保持一致。