题目描述
思路解析动画文字版
记住这句话：先比当前值，再看左孩子对不对得上下一个 voyage，不对就翻转换右子树先走。下面每一帧都在套它。
总览 · 树与目标：先把局面看清。左边这棵树有 5 个节点：根是 50，它的左孩子 30、右孩子 80；30 下面又挂着左孩子 20、右孩子 60。原树的先序（根左右）是 50 30 20 60 80。可目标 voyage 是 50 80 30 20 60，明显对不上，得靠翻转来纠。
总览 · 指针起步：我们用一个指针 i 在 voyage 上从左往右走，初始 i=0，指向第一个值 50。再从根节点开始做先序 DFS：每到一个节点，就拿它的值和 voyage[i] 对一对。指针 i 永远只往前走、不回头。现在出发，先看根 50。
访问 50 · 比较：走到节点 50（紫色）。当前指针 i 指向 voyage 里的 50。先序的第一步永远是看根，所以先判断：节点 50 是不是正好等于 voyage[0]=50？一看就相等，匹配上了。
匹配 50 · i 前移：节点 50 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=1，指向 voyage 里的下一个值 80。接下来这一格，决定了 50 要不要翻转。
看 50 的左孩子：节点 50 有左孩子 30（红框）。先序里，匹配完根之后紧跟的应该是某棵子树的开头，而 voyage[1]=80。关键一问：左孩子 30 等于 80 吗？等于就让左子树先走，不等就得翻转让右子树先走。
翻转 50 !：左孩子 30 并不等于 voyage 要的 80。原样走左子树会立刻对不上，唯一的补救就是翻转节点 50：把它记进答案，并改成「先走右子树、再走左子树」。50 标成翻转色。这样右子树的开头就有机会接上 80 了。
访问 80 · 比较：走到节点 80（紫色）。当前指针 i 指向 voyage 里的 80。先序的第一步永远是看根，所以先判断：节点 80 是不是正好等于 voyage[1]=80？一看就相等，匹配上了。
匹配 80 · i 前移：节点 80 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=2，指向 voyage 里的下一个值 30。接下来这一格，决定了 80 要不要翻转。
叶子 80 · 回上层：节点 80 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
访问 30 · 比较：走到节点 30（紫色）。当前指针 i 指向 voyage 里的 30。先序的第一步永远是看根，所以先判断：节点 30 是不是正好等于 voyage[2]=30？一看就相等，匹配上了。
匹配 30 · i 前移：节点 30 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=3，指向 voyage 里的下一个值 20。接下来这一格，决定了 30 要不要翻转。
看 30 的左孩子：节点 30 有左孩子 20（红框）。先序里，匹配完根之后紧跟的应该是某棵子树的开头，而 voyage[3]=20。关键一问：左孩子 20 等于 20 吗？等于就让左子树先走，不等就得翻转让右子树先走。
不翻转 30：左孩子 20 正好等于 voyage 当前要的 20，说明左子树本来就该排在前面，不用翻转 30。按先序原样「先左子树、再右子树」继续往下走。
访问 20 · 比较：走到节点 20（紫色）。当前指针 i 指向 voyage 里的 20。先序的第一步永远是看根，所以先判断：节点 20 是不是正好等于 voyage[3]=20？一看就相等，匹配上了。
匹配 20 · i 前移：节点 20 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=4，指向 voyage 里的下一个值 60。接下来这一格，决定了 20 要不要翻转。
叶子 20 · 回上层：节点 20 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
访问 60 · 比较：走到节点 60（紫色）。当前指针 i 指向 voyage 里的 60。先序的第一步永远是看根，所以先判断：节点 60 是不是正好等于 voyage[4]=60？一看就相等，匹配上了。
匹配 60 · i 前移：节点 60 正好等于刚才的 voyage 值，匹配成功，它变绿。指针 i 往后走一格，现在 i=5，已经走到 voyage 末尾了。
叶子 60 · 回上层：节点 60 没有左孩子，是个叶子，没有子树需要排序，自然不用翻转。这一枝到此匹配完毕，回到上一层，继续处理还没走的兄弟子树。
完成 · 全部匹配：voyage 指针 i 走到了末尾，途中每个节点都和 voyage 对上了，先序成功对齐。整趟只在节点 50 翻转了一次（因为它的左孩子 30 接不上 voyage 要的 80），节点 30 的左孩子 20 恰好对得上所以没翻。最少翻转点就是 [50]，这就是答案。
回放 · 一条主线：回放一遍这条主线：根 50 匹配后，左孩子 30 对不上目标的 80，翻转 50，先去右边的 80；80 是叶子；回来走 30，30 匹配后它的左孩子 20 正好对上目标的 20，不翻转，依次走 20、60，全部命中。整套就是「值不对立刻判无解，左孩子接不上就翻转」，每步都被 voyage 唯一逼着走，所以翻得最少。
边界先想清：单节点必为 []；根值对不上直接 [-1]；左孩子接不上就在父节点翻一次。
面试重点：讲清每个节点的翻不翻被 voyage 唯一决定，所以局部最优即全局最少。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass 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)，每个节点只在 DFS 里被访问一次，节点内的比较、判断、记录都是 O(1)，n 个节点共 O(n)
- 空间：O(h)，只用递归栈，深度等于树高 h；平衡树 O(log n)，链状极端树最坏 O(n)。答案数组不计入，最多 n 个翻转点也在 O(n) 内
易错点
面试追问把动画讲成自己的话
追问为什么这种「左孩子接不上就立刻翻」的贪心是对的、而且翻得最少？
追问能不能不用递归、改成迭代？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
在二叉树中分配硬币
LeetCode 979 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题