LeetCode上这道“二叉树的前序遍历”题号144难度标着“简单”但我真心建议每一个刷题的人别因为难度标签就轻飘飘带过。前序遍历是二叉树四种遍历前、中、后、层序里的入门动作也是后面几乎所有二叉树题目的地基。递归三行写完谁都会但面试官随便追问一句“不用递归怎么写”或者笔试里给你一棵深度上万的树让你在空间上抠一抠就不是“背个模板”能应付的了。这篇文章我把这道题从头拆到尾递归、迭代、Morris遍历三种方案全部走一遍把每一步操作背后的原因说清楚再把写二叉树程序最常见的运行时错误和排查方法一并梳理掉。不管你是刚开始刷LeetCode热题100还是准备校招面试前临时突击这篇都值得你花二十分钟认真读。1. 题目定位与整体思路1.1 前序遍历到底在干什么先明确前序遍历的定义对一棵二叉树先访问根节点再遍历左子树最后遍历右子树。注意这里“遍历左右子树”内部依然遵循同样的规则所以天然适合用递归来描述。1 / \ 2 3 / \ \ 4 5 6上面这棵树前序遍历的结果是[1, 2, 4, 5, 3, 6]。你可以跟着走一遍先输出1然后进入左子树左子树里先输出节点2再进入它的左子树输出4右子树输出5左子树整棵处理完回到根节点的右子树输出3再输出右子树的右节点6。这个顺序就是“根左右”。注意区分前序遍历强调“访问节点”的动作先于“递归深入子节点”。做序列化、复制二叉树、计算表达式树的值时前序遍历都是最顺手的顺序。这也是它为什么在面试里反复被拿出来问的一个原因——它不只是概念更是很多算法流程的基础组件。1.2 为什么这道简单题值得认真做LeetCode上这道题的正确率不低但很多人是“背过答案”不是“真的理解”。典型的表现递归写法倒背如流一让写迭代解法就卡壳或者明明会两种写法但被问到为什么能用栈、栈里存的到底是什么就答不上来。这道题值得认真做的原因有三个它是理解二叉树遍历统一框架的起点。后面的中序、后序、层序都是在前序的基础上改顺序、换容器前序搞透了其他遍历很快就能顺下来。它是练习“递归转迭代”思路的好素材。递归是系统栈帮你保存状态迭代是自己用栈保存状态这道题刚好能把这两种思维方式打通。它在热题100里属于高频出现的“送分题”但也常被用来当追问的引子。你答得越深面试官越觉得你基础扎实。所以我建议你把它当成一个“面试题活教材”而不是一道做完就删的简单题。下面我们逐层拆解。2. 从递归开始最直观的解法2.1 递归解法怎么写先看最直观的递归实现class Solution: def preorderTraversal(self, 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核心就一句话根 - 左 - 右。当节点为空时直接返回这是递归的出口也是整个递归能够终止的关键。很多刚刷题的人写递归容易犯一个错误递归函数里忘记处理空节点。你想想如果一个节点没有左孩子你直接调用dfs(node.left)传入的是null那函数里第一件事就应该判断if not node: return。这个判断不写程序跑到空节点就会报空指针错误在LeetCode上直接显示Runtime Error。递归过程不需要你手动维护任何中间状态系统栈会自动保存每一层调用现场。这也是递归最舒服的地方写法自然不容易漏逻辑。2.2 递归的时间与空间复杂度时间复杂度是O(n)每个节点恰好被访问一次。空间复杂度是O(h)h是二叉树的高度。这里的空间主要被调用栈占用了。极端情况要特别留意如果是完全二叉树高度h约等于log n空间占用很小。如果树退化成链表形状每个节点只有左孩子递归深度就是n空间开销最大。这也是递归写法一个潜在隐患当二叉树深度非常大时递归可能触发系统栈溢出。LeetCode的用例通常不会让Python的递归深度爆掉但真实工程或者面试手写代码时要能说出这个风险并且知道怎么用迭代解法规避。2.3 递归解法的代码优化上面用的内嵌函数写法足够清晰。如果你想写得紧凑一点也可以把结果数组作为参数传递class Solution: def preorderTraversal(self, root: TreeNode) - List[int]: res [] self._dfs(root, res) return res def _dfs(self, node, res): if not node: return res.append(node.val) self._dfs(node.left, res) self._dfs(node.right, res)两种写法本质一样面试时用你喜欢的那种即可。我个人建议用内嵌函数dfs因为可以少写self.看起来更轻快。3. 迭代解法栈的运用3.1 为什么需要迭代解法面试官追问“能不能不用递归”时真正想问的是你能不能理解递归底层依赖的调用栈并且有能力用显式的数据结构去模拟它。迭代解法的空间复杂度依然是O(h)高度但不会受到系统调用栈导致溢出的影响在一些限制递归深度的场景里更安全。前序遍历迭代的思路是用栈保存“未来需要访问的节点”。因为栈是后进先出而我们想让左子树先被遍历所以压栈时要把右孩子先压下去再压左孩子这样弹出的时候左孩子先被处理就符合“根 - 左 - 右”的顺序了。3.2 最经典的栈实现class Solution: def preorderTraversal(self, 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用前面那棵树模拟一遍栈的变化初始栈[1]。弹出1结果[1]压右3、压左2栈[2, 3]注意栈顶是2。弹出2结果[1, 2]压右5、压左4栈[4, 3, 5]不对这里要小心顺序。压栈时先压右孩子5再压左孩子4所以压完之后栈从栈顶到栈底是[4, 5, 3]。弹出4结果[1, 2, 4]无子节点弹出5结果[1, 2, 4, 5]弹出3结果[1, 2, 4, 5, 3]压右6弹出6完成。整体结果[1, 2, 4, 5, 3, 6]顺序正确。这个写法的关键在于“压栈顺序和访问顺序相反”右孩子先入栈、左孩子后入栈弹出时左先右后。很多初学者容易写反写成了先压左再压右那样输出顺序就变成“根 - 右 - 左”了完全不对。3.3 另一种栈写法沿左链遍历还有一些教材里喜欢用另一种模板先沿着左孩子一路走到底访问节点并压栈然后出栈取右子树继续处理。class Solution: def preorderTraversal(self, root: TreeNode) - List[int]: res [] stack [] cur root while cur or stack: while cur: res.append(cur.val) stack.append(cur) cur cur.left node stack.pop() cur node.right return res这种写法在理解上更加接近“模拟递归展开”的过程。外层的while cur or stack表示当前还有节点要处理或者栈里还存着没处理完的祖先节点。当cur为空时说明已经走到左子树的尽头弹出栈顶的祖先节点转向它的右子树继续。这个模板更有通用性因为把res.append(cur.val)换成不同的位置就能改造成中序、后序遍历。尤其在中序遍历里这种“沿左链压栈”的套路几乎是标配。所以如果时间有限我更推荐你把这个模板吃透。3.4 两种迭代写法的对比写法核心思想压栈策略适用场景左右入栈法先压右、再压左每访问一个节点把它的孩子按“右先进左后进”压栈前序遍历专用代码短沿左链压栈法一路左走到底回溯右子树沿左路径压栈出栈后取右子树中序、前序通用便于迁移这两种写法的时间复杂度都是O(n)空间复杂度也都是O(h)。面试时你挑自己熟练的一种答即可但最好知道另一种的存在因为有时候面试官会指定“用栈模拟递归”来写两种写法都能过。4. Morris遍历把空间压缩到O(1)4.1 线索二叉树的思想如果你把前序遍历的递归调用过程画出来会发现真正占空间的其实是“回溯时要重新找到祖先节点”这个需求。Morris遍历的思路很巧妙它利用叶子节点的空指针临时把左子树最后访问的节点指向当前节点这样就相当于给树动态加了一些“线索”不需要栈也能回溯。这个思想来自“线索二叉树”。线索二叉树的经典做法是把原本为空的左孩子指向中序前驱原本为空的右孩子指向中序后继。Morris遍历在遍历过程中动态创建和删除这种线索所以不需要额外开辟O(h)的栈空间可以达到O(1)的额外空间复杂度。4.2 Morris前序遍历的实现class Solution: def preorderTraversal(self, root: TreeNode) - List[int]: res [] cur root while cur: if not cur.left: # 没有左子树直接访问当前节点转向右子树 res.append(cur.val) cur cur.right else: # 找左子树的最右节点即中序遍历中当前节点的前驱 predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right if not predecessor.right: # 第一次到达前驱建立线索并访问当前节点 predecessor.right cur res.append(cur.val) cur cur.left else: # 线索已存在说明左子树遍历完了恢复指针转向右子树 predecessor.right None cur cur.right return res这段代码相比前面两种会难理解不少。关键有三处第一if not cur.left说明当前节点没有左子树直接访问当前节点并转向右子树因为没有左孩子需要处理。第二当存在左子树时需要先定位“左子树里最靠右的节点”。为什么是最右因为在前序遍历的顺序中当前节点的直接前驱就是“左子树中最后访问的节点”而这个节点一定是左子树中最右边的一个。找到它之后把它原本为空的右指针指向当前节点形成线索。这时访问当前节点然后进入左子树。第三当线索已经存在时说明左子树已经全部遍历完当前节点是第二次到达。我们要把前驱的右指针恢复为None避免对树的临时修改遗留下来然后转向右子树。4.3 Morris遍历的边界情况最容易错的一个点是在找前驱的循环里漏掉predecessor.right ! cur的判断。第一次到达时前驱的右指针为空循环会正常走到最右但第二次到达时前驱的右指针已经指向了当前节点如果没有这个判断就会陷入死循环程序永远跑不完。这是写Morris遍历最经典的坑。另外Morris遍历会临时修改二叉树结构所以在生产环境里如果树是只读的或者有并发访问使用它要格外谨慎。刷题场景下LeetCode会重新给输入用例所以修改树本身不会影响到判题结果但面试时最好主动提一句“Morris遍历会临时改动树结构结束后已经恢复原状”。三种方式对比总结遍历方式时间复杂度额外空间复杂度是否需要修改树可读性递归O(n)O(h)调用栈否最好迭代栈O(n)O(h)否好MorrisO(n)O(1)是结束后恢复较难5. 写二叉树程序时常见的运行时错误排查5.1 空指针与空节点判断LeetCode上做二叉树题报运行时错误最频繁的原因就是空指针。尤其是递归解法里如果对空节点的处理漏掉了程序跑到叶子节点的左右孩子时就会直接崩溃。很多初学者会写出这样的代码def dfs(node): res.append(node.val) # node可能为None直接报错 dfs(node.left) dfs(node.right)正确做法是先判断节点是否为空def dfs(node): if not node: return res.append(node.val) dfs(node.left) dfs(node.right)判断要放在函数入口处而不是调用处。如果你把判断放在调用前代码会变成if node.left: dfs(node.left) if node.right: dfs(node.right)这种写法在逻辑上也能跑通但不优雅而且每次调用都要先问“孩子存不存在”本质上是在把空指针问题推到调用方。LeetCode上的TreeNode在树不完整的情况下node.left或node.right就是None如果你遍历之前没有做任何空判断那就是典型的runtime error来源。5.2 递归栈溢出与递归深度Python默认递归深度上限通常是1000左右。遇到深度很大的树比如退化成一个链的树递归写法可能直接抛RecursionError。在LeetCode里看到RecursionError: maximum recursion depth exceeded就是这个问题。应对方案有几个用迭代解法替代递归显式用栈管理节点不会受系统递归深度限制。如果题目要求必须递归可以尝试调大递归上限但刷题时一般不推荐因为LeetCode的判题环境可能不允许而且这属于治标不治本。在面试中要能主动指出当树高远大于1000时递归写法就有风险迭代或Morris遍历更合适。这里我多说一句面试时你说出“递归深度可能溢出”本身就是加分的因为这证明你不仅会写代码还知道代码在极端情况下的行为。5.3 误修改原始树前面讲的Morris遍历如果不恢复线索指针就永久改变了树的结构。LeetCode会给你全新的测试用例所以看不出来但在实际项目里你的函数可能会被别的地方复用树结构一旦被改坏后续逻辑全乱。解决办法就是每次设置线索后等第二次经过时恢复成None同时在函数开头或结尾做好规划确保函数结束后树结构与原树一致。这也是写Morris遍历必须养成的习惯。还有一种隐蔽的“修改树”问题有人写迭代解法时直接用node node.left往下走如果这颗树之后还要复用那就已经被丢弃了。所以当你只是在“遍历”时尽量保证不修改节点之间的指针关系。5.4 while循环里的死循环陷阱无论是Morris遍历的找前驱循环还是迭代解法里的while cur or stack都有可能出现死循环。最常见的原因是循环条件更新位置错误。比如沿左链压栈的写法while cur or stack: while cur: res.append(cur.val) stack.append(cur) cur cur.left node stack.pop() cur node.right如果你在弹出节点后忘了cur node.right外层循环就会永远处理同一个节点或者提前结束导致结果缺失。这类问题调试起来比较恼火因为代码语法正确逻辑上却是个死循环。排查方法是在纸上画一棵三层的树手动跟踪cur和stack每一步的变化很快就能定位问题出在哪个节点。5.5 输出顺序错乱根左右的顺序记反前序遍历最大的顺序特征是“根在最前”。很多人迭代写法里压栈顺序搞反输出变成了“根右左”或者“根左右但左子树内部顺序乱”。判断办法很简单调试时带着一个三层完全二叉树验证前序遍历的第一个元素必须是根节点第二个必须是根的左孩子。如果你写的迭代版本里左右孩子都压栈后又马上弹出顺序反了整改一下压栈顺序即可。这个错虽然不报错但结果错误容易漏过。错误类型典型表现解决方案空指针访问None的val在递归入口判断空节点递归溢出RecursionError改用迭代解法死循环程序超时检查循环变量是否更新、Morris线索是否复原顺序反了输出结果不符合根左右检查递归访问顺序或压栈顺序6. 常见问题与速查表6.1 这道题和热题100里其他二叉树题的关系LeetCode热题100里二叉树相关的题目占比很高其中遍历类的题目基本都是“套模板”。比如中序遍历把递归里res.append(node.val)的位置移到dfs(node.left)和dfs(node.right)之间。后序遍历把访问动作放到递归两个子函数之后。层序遍历用队列BFS思路按层输出。前序遍历掌握扎实之后中序和后序只需要移动一行代码的位置就能写出来。尤其迭代写法沿左链压栈这个模板直接就能改造成中序把res.append(cur.val)从内层while cur中移出放到弹出节点之后、转向右子树之前。至于热词里提到的“爱吃香蕉的狒狒”LeetCode 873那是一道二分查找题和二叉树没有直接关系。但它在热题里的地位可以类比二分查找是数组题的地基前序遍历是二叉树题的地基。把这两种地基打牢刷题效率会高很多。6.2 线索二叉树和搜索二叉树的关系前面提过Morris遍历基于线索二叉树思想。线索二叉树是把空指针利用起来存放前驱和后继。而搜索二叉树BST是中序遍历有序的二叉树。两者没有必然关系但都是二叉树的高级话题。如果你在面试里说出“Morris遍历借鉴了线索二叉树通过临时线索实现O(1)空间遍历”面试官一般会接着问“那你知道线索二叉树怎么建吗”。你可以简单应对线索化本质上是在遍历过程中记录前驱和后继指针Morris遍历只做了前驱右侧的线索实际线索二叉树还会处理后继。这里不必展开太多但能答出关联性就说明你真的理解。6.3 这道题的调试小技巧写二叉树遍历时调试建议你在本地方便的环境里自己构造一棵测试树然后分步打印。比如Python里可以自己写一个小的树节点构造函数class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right然后构造一棵小树root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) root.right.right TreeNode(6)跑完遍历后把结果手动比一下比直接提交到LeetCode上试错快得多。特别是Morris遍历这种容易死循环的写法麻烦务必调试通过后再提交。6.4 二叉树项目实战中的拓展思考前序遍历的实际应用很多比如序列化二叉树时前序配合空标记可以把二叉树线性化反序列化时重建起来也很方便。所以前序遍历常被用来做树的存储与传输。复制二叉树时先复制根再递归复制左右子树天然就是前序遍历的顺序。LeetCode上有“二叉树的复制”这类题目前序遍历就是底子。表达式树的求值里前序遍历对应的其实是前缀表达式波兰式这个在编译原理里会碰到。如果你刷完这道题后还想继续深入我建议按这个顺序往下走先做中序遍历、后序遍历再做层序遍历然后做“二叉树的最大深度”、“验证二叉搜索树”、“二叉树的最近公共祖先”。这些都跑通了你对二叉树的掌握就超过绝大多数初级面试者了。关于LeetCode周赛这类话题虽然这道题本身不会直接出现在周赛的难题里但周赛的题目往往需要你对基础遍历无比熟悉。我就见过有人周赛时被一道树上DFS题卡住最后发现是自己前序遍历的迭代写法没吃透导致状态维护混乱。多花时间把基础题吃透长远看比多刷难题更值。最后再分享一个我个人的小习惯每道二叉树遍历题做完之后我都会在本地把递归、迭代、Morris三种写法都写一遍并且强制自己给每个版本用一棵三层树手动走一遍流程。这样虽然慢但真的是把“会背代码”变成了“理解代码”。刷题这件事慢就是快。我见过不少朋友一波刷题刷得很猛可一到面试写二叉树题还是心里发虚就是因为没有真正内化这些基础操作。你要是能在这个简单题上多花一点时间后续中序、后序甚至层序都会轻松很多。