前序遍历这道题在LeetCode和力扣上基本上是二叉树入门的第一道坎也是“二叉树的遍历”里最容易被问出花样的考点。不管是刚刷题的新手还是面试前冲刺的求职者前序遍历都是必须彻底吃透的基础操作。这道题本身不难难的是把思路讲清楚、把代码写稳、把复杂度和边界都想明白。我刷题这几年前序遍历相关的题目前前后后写过不下十种解法从最简单的递归到显式栈、标记法、Morris 遍历每一种都有它存在的理由。这篇文章就把我在这道题上的全部经验和踩过的坑整理出来适合刚接触二叉树的人当作入门手册也适合准备面试的人当作复习提纲。1. 二叉树前序遍历的三板斧递归、迭代、统一标记1.1 一道题而已为什么值得单独拎出来讲LeetCode 的二叉树前序遍历题目要求很直接给你一棵二叉树的根节点按前序顺序返回节点的值。前序顺序就是“根节点 - 左子树 - 右子树”所以一棵树一旦展开你第一个读到的永远是根节点。这个特征决定了它在很多二叉树题目里都起着一个“打头阵”的作用树的序列化、树的重建、求树的深度、判断两棵树是否相同这些题的核心逻辑里都能看到前序遍历的影子。真正值得说道的地方在于前序遍历是一道用来区分“会背题”和“真懂题”的经典题目。递归解法三行写出来人人都会但当你被要求用迭代法解不能再动用系统递归栈的时候很多人就开始犯迷糊了。为什么迭代这么麻烦因为前序遍历的顺序是“根先出来然后按左-右处理子树”而不是像层序那样天然匹配队列你需要自己去维护一个数据结构来模拟递归的过程。另外从力扣热题100和周赛的分布来看前序遍历几乎每周都会以各种变形出现在题目里。比如二叉树的直径、二叉树的所有路径、从先序遍历还原二叉树还有在不同语言下运行时错误的排查这些全都是从前序遍历衍生出来的。所以把这道题的多线程解法吃透等于给二叉树问题打了一个牢固的地基。1.2 递归版写法与核心逻辑递归版是最符合直觉的解法。前序遍历的定义本身就是一个递归定义先访问根再访问左子树再访问右子树。def preorderTraversal(root: TreeNode) - List[int]: res [] def dfs(node): if not node: return res.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return res这段代码的核心就是res.append(node.val)放在了递归左子树和右子树之前。别看只是一个位置的区别换到中序和后序就把整棵树的输出顺序全变了。很多人写递归的时候忽略了一点递归函数的返回值设计。上面这个版本用一个res列表在外面承接内部递归只负责往里填逻辑清晰不容易出错。有些同学喜欢让递归函数返回一个列表然后不断拼接比如return [root.val] self.preorderTraversal(root.left) self.preorderTraversal(root.right)这种方式看起来很简洁但每层递归都会创建新列表加上拼接操作实际耗时会明显增加。在力扣那种测试用例规模下递归写法虽然也能过但追求性能的话还是推荐“外置结果容器 原地填充”的方式。递归解法的时间复杂度是 O(n)每个节点恰好被访问一次。空间复杂度是 O(h)其中 h 是树的高度。最坏情况下树退化成链表h 等于 n递归深度为 n这时候在 Python 里可能触发递归层数限制导致RecursionError。这条如果面试官追问“递归版有什么缺陷”你要能够答得上来。1.3 显式栈迭代版写法迭代法的通用思路就是自己维护一个栈把递归过程中系统隐式维护的函数调用栈显式化。前序遍历迭代有一个非常优雅的写法先推根节点入栈然后循环弹出当前节点处理完当前节点后先压右孩子再压左孩子。因为栈是后进先出的右孩子先入栈、左孩子后入栈下一轮循环就会先弹出左孩子正好符合“根 - 左 - 右”的前序顺序。def preorderTraversal(root: TreeNode) - List[int]: if not root: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res这个写法的好处是思路直接几乎不用动脑子。你可以把“先压右再压左”的顺序理解成一种“倒车入库”栈的出口方向是右边你希望左子树先被取出来那就必须让它后进去。但这里有一个常见误区有些人记忆不牢会把压栈顺序写反写成先压左再压右结果输出变成了逆前序。调试的时候如果你发现结果变成了“根 - 右 - 左”不用怀疑大概率就是压栈顺序反了。还有另一个迭代写法是模仿递归的“带状态”写法def preorderTraversal(root: TreeNode) - List[int]: res [] stack [] cur root while cur or stack: while cur: res.append(cur.val) stack.append(cur) cur cur.left cur stack.pop() cur cur.right return res这个写法更贴近中序遍历模板核心是用一个cur指针不停地往左走同时记录路径上的节点等走到最左边空节点时再回溯。虽然它和前一种写法实现方式不同但输出的结果完全一样。我个人倾向于在面试中优先使用第一种写法因为代码更短也更容易和层序遍历做类比。不过第二种写法是理解“递归栈何时收回”的最佳练习建议自己手动模拟几遍。1.4 标记法统一迭代顺手拿下中序和后序前序遍历的显式栈版本虽然简单但有个尴尬的地方它很难直接修改成中序和后序的迭代版本。中序迭代需要处理“先深度往左再取节点再转向右”的流程后序迭代需要两个栈或者对结果反转写法各不相同。如果你准备面试时经常需要从背诵模板切换这个记忆负担是挺重的。解决办法是标记法。它的思路很朴素在栈里压入两种节点一种是需要处理的“待访问节点”一种是已经处理过的“标记节点”。每次从栈里弹出节点时如果是标记节点就直接加入结果如果是普通节点就按“你想要的逆序”把节点重新压回栈。前序遍历的顺序是“根左右”压栈顺序就是“右左根”def preorderTraversal(root: TreeNode) - List[int]: res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: stack.append((node.right, False)) stack.append((node.left, False)) stack.append((node, True)) return res看到这里你会发现它和中序、后序的区别只是重新压栈的三行顺序不同前序右、左、根中序右、根、左后序根、右、左这个模板让三种遍历从“三种完全不同的解法”变成了“同一个模板的三处小改动”特别适合用来应对面试中“换一种顺序再写一遍”的追问。2. 空间复杂度极限挑战Morris 遍历与线索二叉树2.1 从内存优化角度重新审视前序遍历如果有面试官继续追问“你能做到 O(1) 空间复杂度完成前序遍历吗”这时候答案就该从递归、迭代跳到 Morris 遍历了。Morris 遍历的核心思路是利用叶子节点中空闲的左右指针把它们临时改造成指向祖先节点的线索遍历完成后再把线索拆除恢复成原来的二叉树结构。这就是搜索热词里“线索二叉树”的经典使用场景。线索二叉树本来就是一种为了快速找前驱/后继而改造的树结构Morris 遍历相当于在遍历过程中“顺手”把树临时变成线索树用完再还原。为什么能做到 O(1) 空间因为递归版和迭代版都依赖额外的栈来记录回溯路径而 Morris 遍历通过修改叶子节点的指针把这些路径存到了树本身的结构里不需要额外的数据结构。代价就是遍历过程中树被临时修改了如果并发访问这种树会有安全隐患。2.2 前序 Morris 遍历实现细节前序 Morris 遍历的逻辑相对中序稍微多一点判断def preorderTraversal(root: TreeNode) - List[int]: res [] cur root while cur: if cur.left is None: res.append(cur.val) cur cur.right else: predecessor cur.left while predecessor.right and predecessor.right is not cur: predecessor predecessor.right if predecessor.right is None: res.append(cur.val) predecessor.right cur cur cur.left else: predecessor.right None cur cur.right return res这段代码的逻辑可以分成两大块第一如果当前节点cur没有左子树那这里就是前序遍历的一个终点站直接访问它然后往右走。这个过程处理的是在一棵已经遍历完左子树的路径上“向右拐”的动作。第二如果cur有左子树我们需要在左子树里找到最右下的节点这个节点就是中序遍历中cur的前驱。第一次到这个前驱节点时它的右指针还是空的我们就把它指向cur同时记录结果并进入左子树。第二次到同一个前驱节点时说明左子树遍历完了通过这个线索回到了cur这时候需要把线索拆除避免树结构被改坏。这里最容易绕晕的地方就是那个while predecessor.right and predecessor.right is not cur循环。第一次到左子树时这个循环会一路走到最右下的空指针第二次通过线索回到当前层时循环会在predecessor.right is cur停下从而进入到else分支执行“还原线索并右拐”。每次循环结束后树会被完好还原。你可以在代码里构造一棵三层的满二叉树打印出每步cur的轨迹和predecessor的变动亲手走一遍以后就再也不会忘了。2.3 面试里该怎么权衡 Morris 遍历虽然 Morris 遍历的空间复杂度极优但我必须说一个现实情况不到万不得已不建议在一般公司面试中优先写 Morris。原因有三个。第一代码可读性差面试官需要花额外时间去理解你的前驱查找逻辑沟通成本高。第二前序遍历的 Morris 比中序更容易写错尤其是“先输出根还是在找到前驱后输出根”的顺序问题我见过很多人在白板上写到一半把自己绕晕了。第三工程上这种临时修改树结构的遍历方式很少真正派上用场很多编码规范里甚至会标注它为危险操作。但如果是力扣周赛或者双周赛里碰到空间复杂度被卡死的题目或者面试官明确提示“能不能不额外用栈”Morris 就是你展示算法功底的一个亮点。所以我的建议是理解原理、会写模板但别一上来就使用它。3. 复杂度对比与代码的取舍3.1 三种不同解法的复杂度差异解法时间复杂度空间复杂度优点缺点递归O(n)O(h)最坏 O(n)简洁直观适合入门栈溢出风险依赖系统栈显式栈O(n)O(h)最坏 O(n)经典迭代安全可控代码量比递归多标记法O(n)O(n)三种遍历统一模板每个节点额外标记状态MorrisO(n)O(1)空间最优树遍历天花板修改树结构难写难调试从这张表可以看出一个规律时间复杂度的下限就是 O(n)因为这个题至少要访问每个节点一次优化空间全在空间复杂度上。O(1) 空间意味着什么举个例子如果一棵树有十万个节点递归解法和栈解法最多可能占用 O(n) 的辅助存储极端情况下就是十万层的函数调用栈或十万个栈元素内存压力并不小。而 Morris 遍历不管树多大只额外使用常数个指针变量这也是为什么它在某些嵌入式场景和资源受限环境里依然有价值。实际工程里更常采用的还是递归和显式栈。原因很简单可读性优先于极限优化。大多数业务代码里二叉树深度在几千层以上的场景少之又少为了省那点内存去写一个复杂的 Morris 遍历维护成本反而更高。3.2 不同语言实现时的细节差异在 C 里写前序遍历通常用一个vectorint作为结果容器。递归版本里要注意传引用class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint res; dfs(root, res); return res; } void dfs(TreeNode* node, vectorint res) { if (!node) return; res.push_back(node-val); dfs(node-left, res); dfs(node-right, res); } };这里如果漏掉了每次递归都会拷贝整个结果数组一个节点就会产生一次 O(n) 拷贝整棵树的时间复杂度会退化成 O(n^2)。这种错误在实际刷题时很容易被忽略但面试官只看代码一眼就能发现。Java 版本则要注意ListInteger的可变对象引用本身就具有“传地址”的能力所以直接作为参数往里加就行不需要额外包装。另外一个跨语言都适用的坑是节点判空。if not node和if node is None在某些语言里语义不同。Python 里如果节点类实现了__bool__方法行为会自动改变所以最稳妥的写法是显式判断if node is None或者if node is not None。写 C 的人则经常把if (NULL)和if (!node)混用这个在大部分编译器里没问题但工程规范上也会建议显式写if (node nullptr)。4. 写二叉树程序为什么总是报运行时错误排查实录4.1 空指针与节点判空的误区搜索热词里有一条很扎心“写二叉树程序时为什么总是报运行时错误”。这个问题我在刚学树的时候也反复出现过而且答案百分之九十都指向同一类问题没有处理好空节点。最常见的报错场景是这样你想访问root.left.val但当前节点的左孩子其实不存在于是抛出了空指针异常。前序遍历的递归代码里如果入口处不做判空第一层递归可能没问题但当你一路深入到一个空节点时程序就直接崩了。正确做法是两条路线二选一即可入口判空if not root: return []后面递归时调用dfs(node.left)在子递归开头再判一次。单函数递归在递归函数开头判空调用方不用关心子节点是否存在。我之前见过一个典型错误写法把判空写成了这样def preorderTraversal(root): res [] def dfs(node): res.append(node.val) if node.left: dfs(node.left) if node.right: dfs(node.right) if root: dfs(root) return res这段代码看起来没问题但实际上用的是“调用前判空”。如果递归进入一个左子树后继续往左走走到空节点时node为 None然后执行node.val就直接报错了。这种错误特别隐蔽因为它在if node.left成立的那一层是没有问题的直到遇到一个只有右子树没有左子树的节点时才会爆出来。所以统一建议递归函数内部第一行就是判空把“判空”这件事放在边界上而不是调用点。4.2 递归深度爆炸栈溢出与 RecursionError二叉树在前序遍历中运行时错误的第二个高频来源是递归深度。当二叉树是平衡的时候递归深度是 O(log n)非常安全。但如果树退化成一条链比如每个节点都只有右孩子那么递归深度就是 n等于节点数量。LeetCode 测试用例中有些极端场景是一万层甚至十万层的单链树而 Python 的默认递归限制只有 1000 层一碰到就抛RecursionError。解决方向有三个用显式栈迭代遍历彻底不依赖系统递归。如果业务场景允许手动调大递归深度限制但不推荐。检查输入数据是否可能是链状结构必要时先做旋转或扁平化处理。在力扣刷题时最好是直接写出迭代版解法不仅是面试需求也是对自己代码稳定性的负责。4.3 测试用例空树和单节点边界空树是另一个典型的崩溃源。力扣上二叉树的输入可能是root []对应根节点为 null。如果代码里一上来就做root.val操作肯定报错。单节点树则是边界里最容易测试出“结果对不对”的用例前序输出应该正好是一个元素的列表。很多人在写栈迭代版时会因为cur cur.right这行代码在单节点树的情况下多循环一次导致结果多出一个空值。实际上只要保证while stack:的空判断和压栈时有节点才压就不会出错。4.4 关于测试顺序的独家经验调试二叉树程序时我自己的习惯是准备三组固化的自测数据空树[]满二叉树三层七节点比如[1, 2, 3, 4, 5, 6, 7]退化链表[1, null, 2, null, 3, null, 4]这三组数据基本覆盖了正常情况、极浅结构和极深结构。如果再遇到链表超长的情况就再补一组十万个节点的链状数据专门测试空间占用和运行时间。5. 从前序延伸出去热题100、二叉树的深度与层序对比5.1 一个前序递归能顺手解决多少题一旦你真正吃透了前序遍历的递归过程你会发现它跟“二叉树的深度”这道热题几乎是连在一起的。求深度其实就是把前序递归里的res.append(node.val)换成维护当前深度并更新最大值def maxDepth(root: TreeNode) - int: ans 0 def dfs(node, depth): nonlocal ans if not node: return ans max(ans, depth) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) return ans这段代码本质上仍是前序遍历只不过访问节点存值变成更新深度。这就是为什么我强烈建议先把前序遍历写成“框架”再在各种树形问题里复用。同理二叉树的直径、二叉树的所有路径、路径总和、翻转二叉树这些题本质上都是同样的递归回溯框架。有的题是在前序位置做操作有的题是在后续位置做操作核心都是理解“什么时候处理当前节点”以及“子树信息怎么往上传”。5.2 前序和层序的对比栈还是队列热词里把“层序遍历和前序遍历”放在一起也是面试常客。层序遍历的核心数据结构是队列按“从上到下、从左到右”的宽度优先方式逐层访问前序遍历的核心数据结构是栈按根优先的方式深度优先访问。两者代码模板的区别非常清晰# 层序使用队列 if not root: return [] res [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res而前序显式栈版本刚刚已经写过了。对比下来你会发现队列天然的“先进先出”满足层序逐层推进的需求栈天然的“后进先出”满足深度优先的回溯需求。数据结构选型决定了遍历路径这句话在这两道题里体现得淋漓尽致。5.3 力扣热题100和周赛中的前序变体从力扣热门100题的去重统计来看树的遍历类题目占了相当比例而且前序往往不是单独考核而是作为解题步骤之一出现。比如“二叉树的序列化与反序列化”序列化过程本身就是一次前序遍历把节点值依次拼成字符串遇到空节点补一个特殊占位符。反序列化时再按相同顺序重建树。这道题你只会一种遍历顺序是不够的必须把前序遍历和递归切分字符串的思路揉在一起。周赛里则是另一种考法。比如某些题需要你“先遍历整棵树收集信息再根据信息进行二次查询”这时候前序遍历往往作为收集阶段的首选因为它最先获得祖先节点的信息方便做“从上往下传参数”的累计处理。这也解释了为什么前序遍历总是和各种变体题目绑在一起。顺带说一个刷题节奏的经验很多人会在一段时间里只刷树或只刷二分查找然后在不同专题之间切换时明显感觉手感不稳。我自己的做法是隔两周就做一次跨专题穿插练习比如前面可能还在处理“073 爱吃香蕉的狒狒”这种二分查找的题目后面就切回二叉树的遍历题放一起练手。这种来回切换的节奏反而能逼你快速回忆不同算法模板高压环境下周赛才能出手果断。6. 常见问题速查表与一点私人刷题建议6.1 前序遍历高频问题排查表症状可能原因解决方案输出结果是根右左栈迭代时压栈顺序写反改为先压右、再压左结果里多出部分重复节点标记法压栈时未区分访问状态确保处理顺序与目标遍历顺序的逆序一致空树输入直接崩溃缺少判空递归入口与调用点双保险判断递归深度溢出树退化成链状改用显式栈或 Morris 遍历节点值顺序正确但树被改了Morris 遍历线索未拆除确认第二次遇到前驱节点时执行predecessor.right None复杂度超预期递归内拼接列表改用外部容器填充6.2 刷题时的小技巧和节奏感悟最后再多说几句。前序遍历这道题我建议每个准备面试的人至少做到两个要求一是能在 60 秒内写出递归版二是能在 90 秒内写出显式栈迭代版。这两个版本是后续一切变化的基础。若是准备大厂面试最好还能在提示下写出 Morris 遍历的核心逻辑不用全文默写但至少能讲清楚“找前驱、搭线索、拆线索”三步。调试的时候如果输出不对不要急着看答案先打印每一步访问节点和当前栈的状态。比如在显式栈版里每次循环开始前打印stack的内容你会很直观地看到栈里元素的顺序变化。这个方法我在刷二叉树题目时反复使用比自己干瞪眼有效率得多。还有一个小工具建议在本地编辑器里养一个写好的二叉树构建函数能从列表输入快速生成树。LeetCode 上敲代码时往往会自动帮你构建好树但本地调试时并没有这个福利。我早期经常死在这一步后来写了个公共函数只用了一两行代码所有树的题目拿来就能用效率提升非常明显。前序遍历只是二叉树遍历世界的起点但把这个起点走扎实了后面中序、后序、层序、Morris、序列化、搜索二叉树的一切题都会顺利很多。希望这篇记录能帮你在刷题路上少踩几个和我当初一样的坑。