1. 前序遍历到底在前什么很多人在初学二叉树时对前序、中序、后序的划分是死记硬背的前序就是根左右中序就是左根右后序就是左右根。背下来并不难难的是一旦遇到非典型结构或者需要在代码里手写遍历时就会开始纠结到底先访问当前节点还是先递归到左子树这个前字指的是根节点被访问的时机。根节点最先被访问的遍历方式就是前序遍历。它是最直观、也最符合人类认知习惯的一种遍历——看到一个节点先处理它再去管它的左孩子和右孩子。你再想深一层前序遍历本质上是在做一个深度优先的副本输出它可以在不借助额外数据结构的情况下完完整整地把一棵树的结构记录成线性序列。那么它和另外两种遍历的根本差别在哪里我习惯用一个办法把根节点的位置作为锚点。遍历序列的第一个元素如果是整棵树的根节点那这说明这次遍历至少是前序的开头。反过来如果你拿到一棵二叉搜索树的先序序列你甚至可以按照序列顺序一个个插入重新还原出那棵树——这个特性在后文会展开先记住它这是前序遍历在工程里最值钱的地方。现实中前序遍历最典型的场景不是刷题而是树的序列化。一棵二叉树要存进文件或者传到网络另一端你必须把结构信息变成线性数据。前序遍历天然适合干这件事根先出来后面整个片段就是左子树再后面整个片段就是右子树只要配合一个空的占位符还原起来几乎不需要额外状态。这就是为什么很多框架的二叉树序列化方案会选前序而不是中序——中序序列在没有额外标记时根本没法唯一确定一棵树。为了后续讨论方便先给出最基础的前序遍历模板后面所有变体和优化都是从这个骨架出发的。def preorder_traversal(root): result [] def dfs(node): if not node: return result.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return result这段代码是所有前序遍历讨论的起点递归版本三行核心逻辑没有多余动作。但真正理解它的人未必知道这三行代码背后的代价。下面我们就从递归这条最简单路径开始深入。2. 递归实现三行代码背后的调用栈逻辑2.1 递归函数为什么自己调用自己不会死循环很多人刚接触递归时最大的疑惑是dfs左边的子树处理完回到当前函数再进入右边的子树。树本身就是递归定义的——每个节点下面还是树所以用递归处理树是天然匹配的。终止条件node为空就返回保证了递归到叶子节点的空孩子时一定收得住。展开一层调用过程假设现在有个根节点值1左孩子值2右孩子值3。调用preorder_traversal(root)后dfs(root)入栈先把1写进结果然后执行dfs(root.left)——这时候当前函数还没结束它挂在调用栈上等左子树全部处理完才回来。左子树只有节点2于是2写入结果然后dfs(2.left)发现为空返回dfs(2.right)为空返回dfs(root.left)这一行终于执行完了接着才执行dfs(root.right)走到节点3。这个挂起和恢复的过程完全由系统调用栈自动完成你不需要手动记录当前走到哪个节点了、下一步该回到哪里。这是递归最大的优点状态管理交给系统。2.2 时间和空间复杂度为什么是O(n)和O(h)时间上每个节点恰好被访问一次所以总操作次数和节点数n成正比O(n)没有争议。空间上很多人容易答错。递归版的空间复杂度不是O(n)而是O(h)其中h是树的高度。因为任意时刻调用栈里最多同时存在从根到当前叶子的一条链深度就是树高。完全二叉树高度约log n退化成链表时高度等于n所以最坏情况是O(n)。这也是递归实现最大的隐患——一棵严重偏斜的树比如有10万个节点排成一条链递归下去会直接栈溢出。2.3 递归的局限和尾递归优化对树遍历为什么没用有一些语言会对尾递归做优化把递归调用复用当前栈帧避免栈爆炸。但前序遍历的递归不是尾递归——因为第一个递归调用dfs(node.left)结束之后函数还有后半句dfs(node.right)要执行当前栈帧必须保留无法复用。所以不要指望靠写得更尾递归一点来救递归版Python、Java默认都不做这个优化栈溢出的风险始终存在。注意在实际工程里一棵树如果深度可能达到几千层递归版基本就是定时炸弹。这也是我后来在项目里宁愿写迭代版的原因之一——不是递归不好而是在不可控的输入面前迭代版更皮实。3. 迭代实现手动维护栈时最常见的三类翻车现场迭代法要用栈显式模拟递归过程。最常见的写法是这样def preorder_traversal(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result逻辑很紧凑弹出节点访问它然后把右孩子先压栈、左孩子后压栈。因为栈是后进先出先压右意味着左孩子会先被弹出来处理这样就保证了根—左—右的顺序。这里每一步都有讲究下面逐个说。3.1 翻车点一入栈顺序写成先左后右这是新手最经典的错误。如果先把左孩子压栈再把右孩子压栈那么下一次弹出的就是右孩子访问顺序就变成了根—右—左完全错了。很多人在纸面上推导感觉左在前才对吧但忽略了栈的反转特性。要根治这个错误我建议用一个很笨但有效的方法把栈想象成一叠盘子。你希望左孩子先被处理那就让它后进场、压在盘子最上面。右孩子先进场垫底。每次取盘子都是取最上面那个所以左孩子先出栈符合前序要求。3.2 翻车点二栈空判断和空孩子压栈的边界另一个高频问题是写循环时没处理好root本身为空的情况或者把空孩子节点压进栈里导致后面弹出None再访问None.val直接报错。上面的写法在开头就拦截了空根节点同时在压栈前判断左右孩子是否为空避开了这个坑。还有一种思路是不判空直接压弹出时判断stack [root] while stack: node stack.pop() if not node: continue result.append(node.val) stack.append(node.right) stack.append(node.left)这种写法代码更短栈里会多一些None多一轮空转。它有个额外好处是逻辑统一在统一写法处理三种遍历时后面会提到标记法很顺手。两种风格都可以看你习惯。3.3 翻车点三误用队列导致顺序错乱栈和队列在遍历里的差别一句话说清楚栈是深度优先的工具队列是广度优先的工具。有人图省事直接用collections.deque当栈使append和pop都在右端操作这其实还是栈没问题。但如果用了popleft从左端取就变成了层序遍历穿上了迭代版的外衣干的是BFS的活。这个混淆很隐蔽尤其是当树长得比较对称的时候很多测试用例能凑巧蒙混过关只有画个非对称树压测才会暴露。3.4 迭代版的复杂度对比迭代版的时间复杂度同样是O(n)空间复杂度平均为O(h)但最坏情况下栈里最多存储一层的节点数对前序遍历来说其实是O(h)量级——因为栈里始终存储的是当前路径上尚未处理的右孩子们路径最长也就是树高。这点和递归版的栈深度一致但迭代版不会出现函数调用栈溢出的问题使用的是堆内存上限宽裕得多。4. 三种主流写法横向对比从执行效率到代码可读性4.1 标记法一种模板统一三种遍历在LeetCode题解里经常能看到一种标记法也叫颜色标记法用二元组(node, visited)入栈第一次弹出时没访问过就按右、左、根的顺序把根重新标记为已访问后再入栈第二次弹出时直接记录值。这个方法神奇的地方在于只要调整入栈顺序同一个框架可以同时实现前序、中序、后序不用背三套代码。def preorder_traversal(root): WHITE, GRAY 0, 1 result [] stack [(WHITE, root)] while stack: color, node stack.pop() if not node: continue if color WHITE: # 前序根 → 左 → 右入栈顺序反过来右、左、根 stack.append((WHITE, node.right)) stack.append((WHITE, node.left)) stack.append((GRAY, node)) else: result.append(node.val) return result这套写法的代码量比普通迭代版多但它的卖出点是记忆负担小。中序只需要把入栈顺序调成右、根、左后序调成根、右、左。如果要在很短时间里手写多种遍历用这个模板几乎不会出错。缺点也很明显每个节点要入栈两次多了一些额外出入栈开销性能比普通迭代版略低但常数级差距在业务代码中基本无感。4.2 Morris遍历O(1)空间的极限解法前序遍历还有一种更冷门的写法——Morris遍历利用树的大量空闲指针叶子节点的左右指针临时构建线索把空间复杂度压到O(1)。核心思路是每到一个节点找到它左子树中最右的节点把这个最右节点的右指针临时指向当前节点作为回来后继续处理右子树的路标。def preorder_traversal(root): result [] node root while node: if not node.left: result.append(node.val) node node.right else: predecessor node.left while predecessor.right and predecessor.right is not node: predecessor predecessor.right if not predecessor.right: result.append(node.val) predecessor.right node node node.left else: predecessor.right None node node.right return result这个代码初看非常绕我第一次读源码时花了将近半小时才理清。它分三种情况当前节点没有左孩子直接访问当前节点然后转向右孩子当前节点有左孩子就先找到左子树里最右的节点如果它的右指针为空说明左子树还没遍历过把它的右指针指向当前节点记住路标然后访问当前节点进入左子树如果它的右指针已经指向当前节点说明左子树已经走完了这时候把线索恢复为空转向右孩子。Morris遍历的时间复杂度严格说是O(2n)——每个节点的左子树最右节点可能被找多次但摊还下来每个节点被访问常数次所以仍然是O(n)。空间复杂度是O(1)不用栈、不用递归是极限优化场景的答案。但它会临时修改树的结构虽然在结束时全部恢复原样在多线程环境下或者树结构不想被碰的场景里没法用。面试时写出来是明显加分项工程实践中我几乎没见过真拿它跑业务的。4.3 三种写法的选型对照表写法时间复杂度空间复杂度代码量是否修改原树工程推荐度递归版O(n)O(h)最坏O(n)最少否树浅时推荐深度大时慎用迭代版栈O(n)O(h)中等否最推荐稳妥通用Morris遍历O(n)摊还O(1)最多且难以理解遍历期间临时修改面试展示少用于生产标记法O(n)O(h)中等偏多否适合需要统一模板的场合如果让我给一个决策建议常规业务代码用迭代版笔试追求速度可以用递归版统一多种遍历用标记法深度优化且允许改树用Morris。这四种方案之间不存在绝对的优劣核心是搞清楚每种方案的牺牲在哪里。递归牺牲调用栈深度Morris牺牲代码可读性和结构不变性迭代版各方面比较均衡这就是它在工程里成为默认选择的原因。5. 前序遍历在真实业务中的几个落脚点5.1 序列化与反序列化前序序列为什么最适合还原树前面提过前序遍历配合空节点标记可以确定唯一还原一棵二叉树。具体做法遍历时遇到空节点记录为#非空节点记录为节点值序列之间用逗号分隔。还原时按顺序读——第一个非#值一定是根接着递归还原左子树再还原右子树。def serialize(root): result [] def dfs(node): if not node: result.append(#) return result.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ,.join(result) def deserialize(data): values iter(data.split(,)) def build(): val next(values) if val #: return None node TreeNode(int(val)) node.left build() node.right build() return node return build()为什么不用中序因为中序序列只给出节点的相对顺序没有左右子树的边界信息。举个极端例子一棵只有左孩子的链式树和一棵只有右孩子的链式树中序序列完全一样无法区分。前序序列第一个元素锁定了根的位置配合空节点标记递归还原的过程不需要额外参数逻辑非常干净。5.2 表达式树求值前缀表达式的天然生成方式表达式树是一种特殊的二叉树内部节点是运算符叶子节点是操作数。对它做前序遍历得到的就是前缀表达式波兰表达式。前缀表达式的好处是不需要括号也不存在歧义而且求值顺序和遍历顺序完全一致。比如表达式树根是左孩子是*左孩子的左孩子是数字3左孩子的右孩子是数字4右孩子是数字5。前序遍历结果是 * 3 4 5对应中缀就是3 * 4 5。计算前缀表达式可以用一个栈从右往左扫描遇到操作数压栈遇到运算符就弹出两个操作数做运算再压栈。这个特性在编译器前端和一些简单解释器里很常见。5.3 目录结构展示与前端组件树的深度优先遍历一个文件系统的目录树本质上就是一棵多叉树前序遍历对应着先打印当前目录再递归进入子目录的行为。很多命令行工具的树形输出功能就是这么实现的——每往下递归一层缩进就多两个空格。你看到的tree命令输出其实就是带缩进的前序遍历结果。前端场景更明显虚拟DOM是一棵树React的Fiber架构在协调阶段需要深度优先地遍历组件树先处理当前节点执行render或生命周期逻辑再处理子节点这就是一种前序思想的实现。做全链路性能分析时如果你要收集从根组件到每个叶子组件路径上的渲染耗时按前序遍历累加路径总时长数据结构上最自然。5.4 从一棵树上复制结构先拷贝根再递归拷贝左右树的深拷贝也可以用前序框架先创建当前节点的副本再递归拷贝左子树和右子树最后把副本的左右指针接上。这个操作在写不可变数据结构、或者需要从缓存树快速构建一棵工作副本时很实用。def clone_tree(root): if not root: return None new_node TreeNode(root.val) new_node.left clone_tree(root.left) new_node.right clone_tree(root.right) return new_node注意这里和前序序列化的区别序列化输出的线性顺序和拷贝构造的顺序完全一致先处理根、再新节点、再左子树、再右子树。拷贝完成后如果只需要查某棵子树是否存在某个值配合前序遍历还能做短路剪枝——先查根命中直接返回不用深入子树这在树又大又深的时候能省不少时间。5.5 递归转迭代的通用模板思维很多人在处理完树遍历后就认为任务结束了。但前序遍历的迭代实现其实给了一套通用的显式栈模拟递归方法论分析递归函数里每一行代码在何时执行然后想清楚函数调用栈的压栈和弹栈顺序用显式栈配合节点状态或者标记法替代系统调用栈。这套思维可以直接迁移到二叉树的路径求和——迭代版用栈存(节点, 当前路径和)求所有根到叶子的路径——栈里存(节点, 路径列表)N叉树的前序遍历——逻辑几乎一样只是把两个子节点换成孩子列表我在项目里把一个原本递归深度可能到几万层的JSON遍历逻辑改成迭代版之后之前偶发的栈溢出崩溃就再也没出现过。这就是显式栈的价值真正把执行流程握在自己手里。如果只能从这篇文章带走一个点我建议是这句话递归是思维模型迭代是工程兜底前序遍历是理解这两者关系的最佳练习场。
1. 前序遍历到底在前什么很多人在初学二叉树时对前序、中序、后序的划分是死记硬背的前序就是根左右中序就是左根右后序就是左右根。背下来并不难难的是一旦遇到非典型结构或者需要在代码里手写遍历时就会开始纠结到底先访问当前节点还是先递归到左子树这个前字指的是根节点被访问的时机。根节点最先被访问的遍历方式就是前序遍历。它是最直观、也最符合人类认知习惯的一种遍历——看到一个节点先处理它再去管它的左孩子和右孩子。你再想深一层前序遍历本质上是在做一个深度优先的副本输出它可以在不借助额外数据结构的情况下完完整整地把一棵树的结构记录成线性序列。那么它和另外两种遍历的根本差别在哪里我习惯用一个办法把根节点的位置作为锚点。遍历序列的第一个元素如果是整棵树的根节点那这说明这次遍历至少是前序的开头。反过来如果你拿到一棵二叉搜索树的先序序列你甚至可以按照序列顺序一个个插入重新还原出那棵树——这个特性在后文会展开先记住它这是前序遍历在工程里最值钱的地方。现实中前序遍历最典型的场景不是刷题而是树的序列化。一棵二叉树要存进文件或者传到网络另一端你必须把结构信息变成线性数据。前序遍历天然适合干这件事根先出来后面整个片段就是左子树再后面整个片段就是右子树只要配合一个空的占位符还原起来几乎不需要额外状态。这就是为什么很多框架的二叉树序列化方案会选前序而不是中序——中序序列在没有额外标记时根本没法唯一确定一棵树。为了后续讨论方便先给出最基础的前序遍历模板后面所有变体和优化都是从这个骨架出发的。def preorder_traversal(root): result [] def dfs(node): if not node: return result.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return result这段代码是所有前序遍历讨论的起点递归版本三行核心逻辑没有多余动作。但真正理解它的人未必知道这三行代码背后的代价。下面我们就从递归这条最简单路径开始深入。2. 递归实现三行代码背后的调用栈逻辑2.1 递归函数为什么自己调用自己不会死循环很多人刚接触递归时最大的疑惑是dfs左边的子树处理完回到当前函数再进入右边的子树。树本身就是递归定义的——每个节点下面还是树所以用递归处理树是天然匹配的。终止条件node为空就返回保证了递归到叶子节点的空孩子时一定收得住。展开一层调用过程假设现在有个根节点值1左孩子值2右孩子值3。调用preorder_traversal(root)后dfs(root)入栈先把1写进结果然后执行dfs(root.left)——这时候当前函数还没结束它挂在调用栈上等左子树全部处理完才回来。左子树只有节点2于是2写入结果然后dfs(2.left)发现为空返回dfs(2.right)为空返回dfs(root.left)这一行终于执行完了接着才执行dfs(root.right)走到节点3。这个挂起和恢复的过程完全由系统调用栈自动完成你不需要手动记录当前走到哪个节点了、下一步该回到哪里。这是递归最大的优点状态管理交给系统。2.2 时间和空间复杂度为什么是O(n)和O(h)时间上每个节点恰好被访问一次所以总操作次数和节点数n成正比O(n)没有争议。空间上很多人容易答错。递归版的空间复杂度不是O(n)而是O(h)其中h是树的高度。因为任意时刻调用栈里最多同时存在从根到当前叶子的一条链深度就是树高。完全二叉树高度约log n退化成链表时高度等于n所以最坏情况是O(n)。这也是递归实现最大的隐患——一棵严重偏斜的树比如有10万个节点排成一条链递归下去会直接栈溢出。2.3 递归的局限和尾递归优化对树遍历为什么没用有一些语言会对尾递归做优化把递归调用复用当前栈帧避免栈爆炸。但前序遍历的递归不是尾递归——因为第一个递归调用dfs(node.left)结束之后函数还有后半句dfs(node.right)要执行当前栈帧必须保留无法复用。所以不要指望靠写得更尾递归一点来救递归版Python、Java默认都不做这个优化栈溢出的风险始终存在。注意在实际工程里一棵树如果深度可能达到几千层递归版基本就是定时炸弹。这也是我后来在项目里宁愿写迭代版的原因之一——不是递归不好而是在不可控的输入面前迭代版更皮实。3. 迭代实现手动维护栈时最常见的三类翻车现场迭代法要用栈显式模拟递归过程。最常见的写法是这样def preorder_traversal(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result逻辑很紧凑弹出节点访问它然后把右孩子先压栈、左孩子后压栈。因为栈是后进先出先压右意味着左孩子会先被弹出来处理这样就保证了根—左—右的顺序。这里每一步都有讲究下面逐个说。3.1 翻车点一入栈顺序写成先左后右这是新手最经典的错误。如果先把左孩子压栈再把右孩子压栈那么下一次弹出的就是右孩子访问顺序就变成了根—右—左完全错了。很多人在纸面上推导感觉左在前才对吧但忽略了栈的反转特性。要根治这个错误我建议用一个很笨但有效的方法把栈想象成一叠盘子。你希望左孩子先被处理那就让它后进场、压在盘子最上面。右孩子先进场垫底。每次取盘子都是取最上面那个所以左孩子先出栈符合前序要求。3.2 翻车点二栈空判断和空孩子压栈的边界另一个高频问题是写循环时没处理好root本身为空的情况或者把空孩子节点压进栈里导致后面弹出None再访问None.val直接报错。上面的写法在开头就拦截了空根节点同时在压栈前判断左右孩子是否为空避开了这个坑。还有一种思路是不判空直接压弹出时判断stack [root] while stack: node stack.pop() if not node: continue result.append(node.val) stack.append(node.right) stack.append(node.left)这种写法代码更短栈里会多一些None多一轮空转。它有个额外好处是逻辑统一在统一写法处理三种遍历时后面会提到标记法很顺手。两种风格都可以看你习惯。3.3 翻车点三误用队列导致顺序错乱栈和队列在遍历里的差别一句话说清楚栈是深度优先的工具队列是广度优先的工具。有人图省事直接用collections.deque当栈使append和pop都在右端操作这其实还是栈没问题。但如果用了popleft从左端取就变成了层序遍历穿上了迭代版的外衣干的是BFS的活。这个混淆很隐蔽尤其是当树长得比较对称的时候很多测试用例能凑巧蒙混过关只有画个非对称树压测才会暴露。3.4 迭代版的复杂度对比迭代版的时间复杂度同样是O(n)空间复杂度平均为O(h)但最坏情况下栈里最多存储一层的节点数对前序遍历来说其实是O(h)量级——因为栈里始终存储的是当前路径上尚未处理的右孩子们路径最长也就是树高。这点和递归版的栈深度一致但迭代版不会出现函数调用栈溢出的问题使用的是堆内存上限宽裕得多。4. 三种主流写法横向对比从执行效率到代码可读性4.1 标记法一种模板统一三种遍历在LeetCode题解里经常能看到一种标记法也叫颜色标记法用二元组(node, visited)入栈第一次弹出时没访问过就按右、左、根的顺序把根重新标记为已访问后再入栈第二次弹出时直接记录值。这个方法神奇的地方在于只要调整入栈顺序同一个框架可以同时实现前序、中序、后序不用背三套代码。def preorder_traversal(root): WHITE, GRAY 0, 1 result [] stack [(WHITE, root)] while stack: color, node stack.pop() if not node: continue if color WHITE: # 前序根 → 左 → 右入栈顺序反过来右、左、根 stack.append((WHITE, node.right)) stack.append((WHITE, node.left)) stack.append((GRAY, node)) else: result.append(node.val) return result这套写法的代码量比普通迭代版多但它的卖出点是记忆负担小。中序只需要把入栈顺序调成右、根、左后序调成根、右、左。如果要在很短时间里手写多种遍历用这个模板几乎不会出错。缺点也很明显每个节点要入栈两次多了一些额外出入栈开销性能比普通迭代版略低但常数级差距在业务代码中基本无感。4.2 Morris遍历O(1)空间的极限解法前序遍历还有一种更冷门的写法——Morris遍历利用树的大量空闲指针叶子节点的左右指针临时构建线索把空间复杂度压到O(1)。核心思路是每到一个节点找到它左子树中最右的节点把这个最右节点的右指针临时指向当前节点作为回来后继续处理右子树的路标。def preorder_traversal(root): result [] node root while node: if not node.left: result.append(node.val) node node.right else: predecessor node.left while predecessor.right and predecessor.right is not node: predecessor predecessor.right if not predecessor.right: result.append(node.val) predecessor.right node node node.left else: predecessor.right None node node.right return result这个代码初看非常绕我第一次读源码时花了将近半小时才理清。它分三种情况当前节点没有左孩子直接访问当前节点然后转向右孩子当前节点有左孩子就先找到左子树里最右的节点如果它的右指针为空说明左子树还没遍历过把它的右指针指向当前节点记住路标然后访问当前节点进入左子树如果它的右指针已经指向当前节点说明左子树已经走完了这时候把线索恢复为空转向右孩子。Morris遍历的时间复杂度严格说是O(2n)——每个节点的左子树最右节点可能被找多次但摊还下来每个节点被访问常数次所以仍然是O(n)。空间复杂度是O(1)不用栈、不用递归是极限优化场景的答案。但它会临时修改树的结构虽然在结束时全部恢复原样在多线程环境下或者树结构不想被碰的场景里没法用。面试时写出来是明显加分项工程实践中我几乎没见过真拿它跑业务的。4.3 三种写法的选型对照表写法时间复杂度空间复杂度代码量是否修改原树工程推荐度递归版O(n)O(h)最坏O(n)最少否树浅时推荐深度大时慎用迭代版栈O(n)O(h)中等否最推荐稳妥通用Morris遍历O(n)摊还O(1)最多且难以理解遍历期间临时修改面试展示少用于生产标记法O(n)O(h)中等偏多否适合需要统一模板的场合如果让我给一个决策建议常规业务代码用迭代版笔试追求速度可以用递归版统一多种遍历用标记法深度优化且允许改树用Morris。这四种方案之间不存在绝对的优劣核心是搞清楚每种方案的牺牲在哪里。递归牺牲调用栈深度Morris牺牲代码可读性和结构不变性迭代版各方面比较均衡这就是它在工程里成为默认选择的原因。5. 前序遍历在真实业务中的几个落脚点5.1 序列化与反序列化前序序列为什么最适合还原树前面提过前序遍历配合空节点标记可以确定唯一还原一棵二叉树。具体做法遍历时遇到空节点记录为#非空节点记录为节点值序列之间用逗号分隔。还原时按顺序读——第一个非#值一定是根接着递归还原左子树再还原右子树。def serialize(root): result [] def dfs(node): if not node: result.append(#) return result.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ,.join(result) def deserialize(data): values iter(data.split(,)) def build(): val next(values) if val #: return None node TreeNode(int(val)) node.left build() node.right build() return node return build()为什么不用中序因为中序序列只给出节点的相对顺序没有左右子树的边界信息。举个极端例子一棵只有左孩子的链式树和一棵只有右孩子的链式树中序序列完全一样无法区分。前序序列第一个元素锁定了根的位置配合空节点标记递归还原的过程不需要额外参数逻辑非常干净。5.2 表达式树求值前缀表达式的天然生成方式表达式树是一种特殊的二叉树内部节点是运算符叶子节点是操作数。对它做前序遍历得到的就是前缀表达式波兰表达式。前缀表达式的好处是不需要括号也不存在歧义而且求值顺序和遍历顺序完全一致。比如表达式树根是左孩子是*左孩子的左孩子是数字3左孩子的右孩子是数字4右孩子是数字5。前序遍历结果是 * 3 4 5对应中缀就是3 * 4 5。计算前缀表达式可以用一个栈从右往左扫描遇到操作数压栈遇到运算符就弹出两个操作数做运算再压栈。这个特性在编译器前端和一些简单解释器里很常见。5.3 目录结构展示与前端组件树的深度优先遍历一个文件系统的目录树本质上就是一棵多叉树前序遍历对应着先打印当前目录再递归进入子目录的行为。很多命令行工具的树形输出功能就是这么实现的——每往下递归一层缩进就多两个空格。你看到的tree命令输出其实就是带缩进的前序遍历结果。前端场景更明显虚拟DOM是一棵树React的Fiber架构在协调阶段需要深度优先地遍历组件树先处理当前节点执行render或生命周期逻辑再处理子节点这就是一种前序思想的实现。做全链路性能分析时如果你要收集从根组件到每个叶子组件路径上的渲染耗时按前序遍历累加路径总时长数据结构上最自然。5.4 从一棵树上复制结构先拷贝根再递归拷贝左右树的深拷贝也可以用前序框架先创建当前节点的副本再递归拷贝左子树和右子树最后把副本的左右指针接上。这个操作在写不可变数据结构、或者需要从缓存树快速构建一棵工作副本时很实用。def clone_tree(root): if not root: return None new_node TreeNode(root.val) new_node.left clone_tree(root.left) new_node.right clone_tree(root.right) return new_node注意这里和前序序列化的区别序列化输出的线性顺序和拷贝构造的顺序完全一致先处理根、再新节点、再左子树、再右子树。拷贝完成后如果只需要查某棵子树是否存在某个值配合前序遍历还能做短路剪枝——先查根命中直接返回不用深入子树这在树又大又深的时候能省不少时间。5.5 递归转迭代的通用模板思维很多人在处理完树遍历后就认为任务结束了。但前序遍历的迭代实现其实给了一套通用的显式栈模拟递归方法论分析递归函数里每一行代码在何时执行然后想清楚函数调用栈的压栈和弹栈顺序用显式栈配合节点状态或者标记法替代系统调用栈。这套思维可以直接迁移到二叉树的路径求和——迭代版用栈存(节点, 当前路径和)求所有根到叶子的路径——栈里存(节点, 路径列表)N叉树的前序遍历——逻辑几乎一样只是把两个子节点换成孩子列表我在项目里把一个原本递归深度可能到几万层的JSON遍历逻辑改成迭代版之后之前偶发的栈溢出崩溃就再也没出现过。这就是显式栈的价值真正把执行流程握在自己手里。如果只能从这篇文章带走一个点我建议是这句话递归是思维模型迭代是工程兜底前序遍历是理解这两者关系的最佳练习场。
