LeetCode 题解工作台
翻转二叉树以匹配先序遍历
给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。 另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。 通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以通过深度优先搜索的方式遍历整棵树，用一个下标 记录当前遍历到的节点在数组 中的下标，如果当前遍历到的节点的值不等于 ，那么说明翻转后无法匹配，我们标记 为 `false`，并直接返回。否则，我们将 的值加 ，然后判断当前节点是否有左子节点，如果没有，或者左子节点的值等于 ，那么我们递归遍历当前的左右子节点；否则，我们需要翻转当前节点，然后再递归遍历当前的右子节点和左子节点。 搜索结…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 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.length1 <= n <= 1001 <= Node.val, voyage[i] <= n- 树中的所有值 互不相同
voyage中的所有值 互不相同
解题思路
方法一：DFS
我们可以通过深度优先搜索的方式遍历整棵树，用一个下标 记录当前遍历到的节点在数组 中的下标，如果当前遍历到的节点的值不等于 ，那么说明翻转后无法匹配，我们标记 为 false，并直接返回。否则，我们将 的值加 ，然后判断当前节点是否有左子节点，如果没有，或者左子节点的值等于 ，那么我们递归遍历当前的左右子节点；否则，我们需要翻转当前节点，然后再递归遍历当前的右子节点和左子节点。
搜索结束后，如果 为 true，那么说明翻转后可以匹配，我们返回答案数组 ，否则返回 。
时间复杂度 ，空间复杂度 。其中 是树中的节点数目。
# 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(root):
nonlocal i, ok
if root is None or not ok:
return
if root.val != voyage[i]:
ok = False
return
i += 1
if root.left is None or root.left.val == voyage[i]:
dfs(root.left)
dfs(root.right)
else:
ans.append(root.val)
dfs(root.right)
dfs(root.left)
ans = []
i = 0
ok = True
dfs(root)
return ans if ok else [-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Expect questions about correctly tracking voyage index during recursive traversal.
- question_mark
Watch for prompts about minimal flip sets and early failure detection.
- question_mark
Interviewers may ask for explanations of why certain flips are necessary or redundant.
常见陷阱
外企场景- error
Not updating the voyage index correctly during recursion, causing false failures.
- error
Flipping nodes unnecessarily instead of only when the left child mismatches.
- error
Failing to handle edge cases where matching the voyage is impossible, returning incorrect results.
进阶变体
外企场景- arrow_right_alt
Count the total number of flips needed instead of returning the flipped node list.
- arrow_right_alt
Return a boolean indicating if the voyage can be matched without returning nodes.
- arrow_right_alt
Apply the same approach to mirrored post-order or in-order sequences with flips.