AlgoNote 算法题解：0971 翻转二叉树以匹配先序遍历——基于 DFS 指针的贪心匹配详解

• 教程
• 文档
• 知识库

本篇题解围绕 LeetCode 0971「翻转二叉树以匹配先序遍历」展开，结合「算法通关手册（AlgoNote）」仓库中的二叉树遍历与递归专题内容，系统讲解如何在先序遍历框架下用深度优先搜索（DFS）配合单一游标指针完成「最少翻转」的贪心匹配。读完本文，你将掌握一类「按遍历顺序边匹配边决策」的二叉树问题解法：如何判断不可行、如何记录翻转节点、以及如何把递归代码的每一步与算法正确性一一对应。

题目概述：一道融合「先序遍历 + 翻转 + 匹配」的中等题

• 题目编号：0971（LeetCode）
• 标签：树、深度优先搜索、二叉树
• 难度：中等

这道题在 AlgoNote 仓库中位于题解目录 docs/solutions/0900-0999，同时被收录在仓库的分类题目清单中，归属于「二叉树的前序遍历」与「递归算法」等专题之下，适合在学完二叉树基础遍历后作为进阶练习。

它的特别之处在于：普通遍历题只是「读出」树的形状，而本题要求「修改」树（通过交换节点的左右子树）去凑出一个给定的遍历序列，并且要保证翻转次数最少。这既考察前序遍历的本质理解，也考察递归 + 贪心的组合运用。

题目理解：问题描述、输出要求与数据约束

问题描述

给定一棵二叉树的根节点root，树中共有n个节点，每个节点都有一个不同于其他节点且处于1到n之间的值（即节点值恰好构成1..n的一个排列）。

同时给定一个由n个值组成的行程序列voyage，它表示「预期」的二叉树先序遍历结果。

**翻转（Flip）**的定义是：交换某个节点的左右子树。例如翻转节点 1，就是指把节点 1 的左子树与右子树互换位置。

输出要求

请翻转最少的节点，使这棵二叉树的先序遍历结果与voyage完全匹配：

• 如果可行：返回被翻转过的所有节点的值组成的列表，顺序不限；
• 如果不可行：返回列表[-1]。

数据约束

注意n ≤ 1000，意味着递归深度最坏为 1000，使用递归实现是安全的；两个序列中值互不相同，保证了我们总是可以用「值」来唯一标识一个节点。

示例解析

示例 1：不可匹配

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

根节点值为1，但voyage的首个元素是2，根节点值对不上预期序列的第一个值，因此无论怎么翻转都无济于事，直接判定不可行，返回[-1]。

示例 2：翻转单个节点即可匹配

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

原始树的前序遍历为[1, 2, 3]，期望为[1, 3, 2]。根节点1匹配后，下一个期望值是3，而左子树根节点是2，不匹配，说明需要翻转节点1（交换其左右子树）。翻转后前序遍历变为[1, 3, 2]，匹配成功，因此返回被翻转节点值组成的列表[1]。

核心思路：在先序遍历的骨架上做贪心决策

前置知识：什么是先序遍历

本题的一切判断都建立在先序遍历的定义之上：按照「根节点 → 左子树 → 右子树」的顺序访问所有节点。仓库文档 docs/05_tree/05_02_binary_tree_traverse.md 给出了先序遍历的完整定义、递归实现与显式栈实现：

• 如果二叉树为空，直接返回；
• 否则依次：访问根节点 → 递归先序遍历左子树 → 递归先序遍历右子树。

先序遍历结果中，根节点之后紧跟着的就是其左子树（若存在）的先序序列。这一性质是本题判断「何时需要翻转」的直接依据。

关键洞察：每个节点只有一种「必要」决策

翻转一个节点只会影响它两个孩子的访问先后顺序，不会影响更宏观的序列结构。因此在 DFS 过程中，当访问到某个节点、其值已经与voyage当前位置匹配后，接下来的唯一问题就是：下一个期望值应该来自左孩子还是右孩子？

• 若左孩子存在且其值恰好等于下一个期望值，说明按「先左后右」的自然顺序即可，无需翻转；
• 否则，为了让序列继续匹配，只能选择翻转当前节点（交换左右孩子），使右孩子先被访问。

注意：一旦左孩子存在且值不等于下一个期望值，那么「先左后右」必然失败，此时翻转是唯一可行解，不存在「翻不翻转」的自由选择——这正是贪心正确性的根源：每次翻转都是被当前序列「逼迫」的，因此累计的翻转次数天然最少。

游标指针 index

DFS 过程中维护一个指针index，指向voyage中「当前应匹配的位置」：

1. 每成功匹配一个节点的值，index就前进一位；
2. 下一个要检查的节点（无论是左孩子还是右孩子）必须与voyage[index]相等；
3. 若任意节点值与期望位置的值不一致，立即宣告失败。

由于n == voyage.length且所有值互不相同，只要整棵树的值按正确的访问顺序全部匹配，index恰好会在结束时指向n，不会出现「匹配完但还剩节点」或「节点访问完但序列还有剩余」的错位。

算法流程：带 index 指针的深度优先搜索

按照仓库 docs/07_algorithm/07_02_recursive_algorithm.md 中总结的递归「三步法」（写递推公式 → 确定终止条件 → 翻译为代码），可以将本题的递归逻辑拆解如下：

1. 基本情况（终止条件）：当前节点为空，直接返回True（空子树无需匹配，也不消耗index）。
2. 值匹配检查：若当前节点的值不等于voyage[index]，说明序列在此处断裂，返回False。
3. 推进指针：当前节点匹配成功，index加 1。
4. 递归决策：
   • 若左孩子存在且左孩子值与voyage[index]相等 → 按正常顺序「先左后右」递归；
   • 否则 → 记录当前节点值为「被翻转节点」，并改为「先右后左」递归。
5. 汇总结果：整棵 DFS 全部返回True则输出翻转列表，否则输出[-1]。

完整代码实现（Python）

# 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]: self.flipped = [] # 记录被翻转的节点值 self.index = 0 # 指向 voyage 中当前应匹配的位置 def dfs(node): if not node: return True # 空节点：无需匹配，不消耗 index # 1. 当前节点值必须与期望位置一致 if node.val != voyage[self.index]: return False # 2. 匹配成功，指针前进 self.index += 1 # 3. 若左孩子存在且值不是下一个期望值，则必须翻转当前节点 if node.left and node.left.val != voyage[self.index]: # 记录被翻转的节点 self.flipped.append(node.val) # 翻转后先遍历右子树，再遍历左子树 return dfs(node.right) and dfs(node.left) # 4. 正常顺序：先左后右 return dfs(node.left) and dfs(node.right) # 匹配成功返回翻转列表，失败返回 [-1] if dfs(root): return self.flipped else: return [-1]

关键代码行为解读

• return dfs(node.right) and dfs(node.left)的短路顺序：Python 的and从左到右求值，因此这里会先递归dfs(node.right)再递归dfs(node.left)，与翻转后「先右后左」的访问顺序严格一致，index的推进也随之保持同步；无论哪一侧失败，and都会让整体返回False。
• index的推进时机：只有「值匹配成功」的节点才会推进指针，空节点不推进。这保证了指针位置永远指向下一个「尚未消费」的期望值。
• 翻转记录的语义：题目只要求返回「被翻转节点」的值，并不要求按任何特定顺序，因此 DFS 过程中按访问顺序追加即可。

正确性分析

1. 局部决策唯一性：在节点值匹配成功的前提下，若左孩子存在且与下一个期望值不等，那么「先左后右」必然让序列在此处失配，唯一出路就是翻转；若左孩子为空，则不存在「需要翻转」的分支判断，直接按顺序递归（dfs(None)恒为True，实际匹配落在右子树上）。
2. 贪心即最优：因为每次翻转都是被当前voyage序列强制要求的，不存在「少翻一次也能匹配」的替代方案，所以按此策略累计的翻转集合就是满足条件的最小集合。
3. 失败判定的完备性：只要存在任意一次值失配（包括根节点本身与期望序列首位不一致的情形，如示例 1），递归链最终返回False，主函数据此输出[-1]，与题目要求一致。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是树中节点总数。每个节点最多被访问一次，指针与翻转记录的操作均为常数时间。
• 空间复杂度：$O(h)$，其中 $h$ 是树的高度。空间消耗来自递归调用栈的深度，最坏情况下（树退化为链状）$h = n = 1000$，递归深度在题目数据范围内是安全的。

边界情况与注意事项

• 单节点树：root = [1]、voyage = [1]时，根节点匹配后index越界保护由递归结构天然规避——左右孩子均为空，dfs(None)直接返回True，输出[]（无需翻转）。
• 只有右子树、没有左子树：此时node.left为None，不会进入翻转分支，按「先左后右」顺序递归时左孩子为空直接通过，真正匹配右子树即可。
• 翻转后仍失败：例如左孩子值不匹配，翻转后右子树的值仍与期望不符，则dfs(node.right)返回False，整体输出[-1]，不会把错误的翻转列表返回给用户。

与仓库中相关题目的衔接

本题与仓库内多篇题解形成完整的「翻转 / 遍历」知识闭环，建议按顺序对照学习：

• 0144. 二叉树的前序遍历：先序遍历的递归与显式栈实现，是理解本题匹配逻辑的底层基础；
• 0226. 翻转二叉树：无条件翻转整棵树的左右子树（简单题），与本题「按需最少翻转」形成对比，可体会「无条件翻转」与「条件性贪心翻转」的差别；
• 0951. 翻转等价二叉树：判断两棵树是否「翻转等价」，与本题同属「翻转」主题，可一并练习；
• 05_02_binary_tree_traverse.md：二叉树四种遍历方式的系统讲解；
• 07_02_recursive_algorithm.md：递归三步法与栈溢出、记忆化等注意事项，为分析本题递归实现提供方法论支撑。

总结

LeetCode 0971 的本质是「在先序遍历的序列约束下做最小翻转」：利用 DFS 维护一个指向voyage的游标指针，逐节点比对值，一旦左孩子与下一个期望值不符就强制翻转并记录，最终把「能否匹配」转化为递归链上的真值传播。其时间复杂度 $O(n)$、空间复杂度 $O(h)$，代码结构清晰，非常适合作为「树 + DFS + 贪心」三类考点的综合训练题。结合 AlgoNote 仓库中先序遍历与递归专题的学习资料，可以一次性打通「遍历 → 匹配 → 修改树结构」的完整思维链路。

• 教程
• 文档
• 知识库