刚开始刷二叉树的时候我一度以为自己永远记不住这三道题的代码。LeetCode 144、145、94前序遍历、后序遍历、中序遍历递归版本三分钟写完迭代版本一写就卡壳尤其是中序和后续每次对着空栈发呆总觉得逻辑在脑子里是通的落到代码上就全是问题。后来跟着代码随想录的训练营刷到第十三天把的递归遍历和迭代遍历从头到尾捋了一遍又把102题层序遍历加了进来才真正理解了“遍历顺序”这件事的本质。这篇东西就是给我的刷题笔记做个沉淀。如果你也处在“递归能写但迭代总卡”的阶段或者刚准备开始刷二叉树我尽量把每一行代码背后的为什么讲清楚。文章里有完整的解题模板、复杂度分析还有我踩过的几个坑希望能让你少走点弯路。1. 递归遍历先想清楚这三件事前中后序随便写递归版本是二叉树遍历的起点也是后边所有写法的根基。LeetCode 144、145、94三道题的递归解法本质上是在同一个模板里换三行代码的顺序所以别把三道题当成三个知识点去背当成一个知识点去理解就好。1.1 为什么空节点返回是递归的“刹车”先看最基础的递归模板拿前序遍历举例def preorderTraversal(root): if not root: return [] res [root.val] res preorderTraversal(root.left) res preorderTraversal(root.right) return res很多人刚写递归的时候第一反应是“我要用一个全局数组来收集结果”然后在递归函数里不断append。但你看上面这种写法每一层递归都返回一个列表往上层层拼接最后整棵树的结果就出来了。这个写法的好处是不需要额外定义一个成员变量函数本身就是纯函数刷题和面试的时候都不容易写出bug。这里的if not root不是可有可无的边界条件它是整个递归的“刹车”。二叉树的递归遍历本质上是在模拟一条从根节点出发、不断往下走、走到尽头再回头的过程。如果没有这辆“刹车”函数会一直往None的孩子节点里钻直到栈溢出。你可以把它理解成递归里的base case到达空节点说明这条路走到了头该掉头回去了。1.2 三序遍历其实只有一行代码的差别前序、中序、后序这三个名字描述的是“根节点”在什么时候被处理前序先处理根再处理左子树最后处理右子树简称中左右。中序先处理左子树再处理根最后处理右子树简称左中右。后序先处理左子树再处理右子树最后处理根简称左右中。把三个递归版本放在一起看区别就更明显了def preorderTraversal(root): # 中左右 if not root: return [] res [root.val] res preorderTraversal(root.left) res preorderTraversal(root.right) return res def inorderTraversal(root): # 左中右 if not root: return [] res [] res inorderTraversal(root.left) res.append(root.val) res inorderTraversal(root.right) return res def postorderTraversal(root): # 左右中 if not root: return [] res [] res postorderTraversal(root.left) res postorderTraversal(root.right) res.append(root.val) return res看到没有三份代码几乎一样区别只在于res.append(root.val)这一句的位置在最前面就是前序在中间就是中序在最后就是后序。递归遍历的核心逻辑是统一的每次处理一个节点先递归左子树再递归右子树根节点的处理顺序决定遍历顺序。这里我建议大家动手画一棵三层的二叉树比如1为根、2和3分别为左右孩子、4是2的左孩子然后分别按三种顺序在图上标注节点被“读到”的顺序。画完之后你会发现前序是“从上往下先左后右”中序是“从左往右先下后上”后序是“从下往上先左后右”。这个直观感觉比背口诀重要得多。1.3 递归的时间与空间复杂度别只记结论三道递归解法的时间复杂度都是O(n)因为每个节点恰好被访问一次。空间复杂度是O(h)h是树的高度。这个h在最坏情况下可能是n比如一棵只有左孩子的链式树递归深度就达到了n在平衡二叉树里h大约是log n。所以递归的空间复杂度不是固定的O(n)而是取决于树长什么样。很多题解直接写“空间复杂度O(n)”是为了简化描述准备的退化成链表的最坏情况。面试的时候如果被追问能说清楚“递归深度等于树高”这一层会显得你对本原理是真懂了。2. 迭代遍历一个栈怎么同时驾驭前序和中序递归能解决的问题迭代基本都能解决因为递归本身就是在隐式地使用函数调用栈。迭代遍历就是把这个栈从系统手里拿过来自己显式地维护。这也是LeetCode 144、145、94三道题里最常见的一类进阶考法不让你用递归强制你用迭代。2.1 前序的“右左入栈”为什么能保证顺序前序遍历迭代写法是三个里面最简单的def preorderTraversal(root): if not root: return [] stack [root] res [] 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关键就在最后两个if的顺序先压右孩子再压左孩子。因为栈是后进先出弹出的顺序会和压入的顺序相反。你希望弹出顺序是“先左后右”就得让右孩子先进栈、左孩子后进栈这样左孩子会被先弹出。记住一个口诀前序迭代就是“中左右入栈右左”。每一轮循环做的事情其实很单纯弹出栈顶节点并记录值然后把这个节点的右孩子、左孩子依次压入栈。栈保证了我们永远先处理左子树这一支等左子树整支处理完栈中自然剩下的就是之前压入的各个右子树节点。我第一次写这个解法时犯过一个错先压左孩子再压右孩子结果顺序变成根、右子树、左子树整棵树的顺序全乱了。后来想明白了栈的特性这个坑就再也没踩过。2.2 中序为什么要一路压左链中序迭代比前序难一个档次因为它不是简单的“弹出就处理”。看代码def inorderTraversal(root): if not root: return [] stack [] cur root res [] while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res这里最核心的是内层那个while cur循环它的作用是把当前节点到它的最左叶子这一条链路上的所有节点全部压入栈。为什么因为中序是左中右我们必须先处理一棵子树最左边的节点然后才能往回处理它的父节点。用一个生活场景来类比中序遍历就像你要从一棵树的最左下角开始一格一格往右上方扫过去。遇到每一个节点你不能立刻处理它因为它的左子树还没扫完所以你必须先把节点记在栈里继续往下钻左子树。钻到最左边没有左孩子了这时候才从栈里弹出这个最左节点处理它然后转向它的右子树重复同样的逻辑。整个过程可以概括为三句话一直往左压栈弹出并处理转向右子树。很多教程会把这套写法直接甩给你但如果你不理解“为什么要一路压栈”你很难在考场上默写出来。理解了之后每一次cur cur.right都是在说“左子树处理完了根也处理完了该轮到我这一侧的右子树了。”2.3 迭代写法的空指针雷区迭代写法的bug高发区有两个。第一个是前序里忘记判断节点是否存在。有些同学会写成if node.right: stack.append(node.right) if node.left: stack.append(node.left)漏掉if判断直接把空指针压进栈里循环里就会对None取.val直接报AttributeError。其实这道题里用if判断还是if root初始化两种风格都能过但不能夹在中间造成逻辑混乱。第二个是中序初始化时if not root: return []和cur root这两个条件缺一不可。如果没有最外层的空树判断while cur or stack在root为空时会直接跳过循环返回空数组结果其实也是对的但如果你想省掉判断得确保stack的初始状态没问题。代码风格上我建议保留明确的空树判断可读性更好面试的时候也更容易讲清楚。3. 后序遍历的取巧路径前序反转法与标记位写法后序迭代是所有二叉树遍历里最让人头大的一个。网上的主流解法至少有三种我先讲最取巧的一种再说一种我自己后来最常用的写法。3.1 前序反转为什么成立先看这段代码def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]你可以把它理解成“前序遍历的镜像版”前序是“中左右”这里先按“中右左”的顺序收集结果所以先压左孩子再压右孩子让右子树先出栈最后把整个结果数组反转就变成了“左右中”也就是后序遍历。为什么反转一下就成立了因为后序是左右中它和前序的中左右正好是镜像对称的。你按中右左的方式收集得到的结果反转过来恰好就是左右中。这个方法在面试里非常实用因为代码量跟前序几乎一样只需要改一下两个if的顺序再在最后加一个反转。反转整列表的时间复杂度是O(n)加上前面遍历的O(n)整体还是O(n)不影响大O级别。空间上多了一个res数组存结果这部分本来就是答案需要占用的空间不算额外开销。3.2 标记位写法用None统一三种遍历除了前序反转还有一种“标记位”写法也是代码随想录教程里重点推荐的路子。它的核心思路是每次把节点压入栈时同时在它后面压一个标记当这个标记被弹出时说明这个节点的左右子树已经处理完了可以输出这个节点本身了。def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() if node: stack.append(node) stack.append(None) # 标记表示node已经可以输出了 if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res你可能会问前序和中序是不是也能用同一种套路完全可以只需要调整节点、标记、左右孩子入栈的顺序。标记位写法的本质是用一个额外的None元素模拟递归的“函数返回”动作。递归里函数处理完一棵子树后会自动回到上一层迭代写法没有这个自动机制所以需要自己往栈里塞一个“返回点”。这种写法的好处是模板统一三种遍历只需要调整压栈顺序。坏处是代码看起来有点绕第一次看容易懵。我建议先用前序反转法把后序遍历跑通等对栈的操作足够熟悉了再来体会标记位写法的精妙。3.3 我后来为什么倾向于标记位写法说实话如果只是为了AC一道题前序反转法更短、更不容易写错。但我后来在做一些二叉树相关的综合题时发现标记位写法更接近递归的思考方式它的入栈顺序是从“最迟到处理”的逻辑倒推的只要把递归里“左、根、右/左、右、根”的访问顺序翻译成入栈顺序就行不容易陷入“中序那个while循环怎么控制”的困惑里。另外一点标记位思路对理解其他需要遍历顺序的题目也有帮助。比如二叉树最近公共祖先、二叉树展开为链表这类题目不要求纯按后序输出但需要用“先孩子后自己”的处理次序标记位写法体现出的“延迟处理”思想就很有用了。这里也提一句网上还能看到“双栈法”解决后序遍历思路是先遍历得到中右左再用另一个栈反转。原理和前序反转法完全一样我个人觉得有一个就够用了。4. 层序遍历一个队列解决的不只是102这道题LeetCode 102是一道“看起来基础、实际上能延伸出一大堆题”的典型代表。层序遍历的写法套路很固定但理解清楚它为什么用队列以及怎么控制“一层”的范围比背代码重要得多。4.1 为什么层序必须用队列先看基础代码from collections import deque def levelOrder(root): if not root: return [] q deque([root]) res [] while q: level [] for _ in range(len(q)): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res层序遍历和前中后序的最大区别是它不是深度优先而是广度优先。深度优先用栈因为要一条路走到黑再回头广度优先用队列因为要一层一层地平推。这是“用什么数据结构”的根本依据不要死记。想象一下你手头有一个队列初始时只有根节点。你把根节点从队头取出来把它左右两个孩子从队尾放进去。第二轮循环队列里的两个孩子会被依次取出同时它们各自的孩子又会被放进队尾。每一轮队列里装的恰好就是某一层的节点你从队头取走老节点从队尾放进去新节点先进先出自然保证了“同一层按从左到右的顺序输出”。4.2 用size固定每层范围初学者容易写错的地方是不知道每层有多少个节点直接把while q写成while q把所有节点一股脑输出层与层之间就混在一起了。上面代码里的for _ in range(len(q))是控制一层的边界。关键点在于进入for循环时len(q)记录的是当前层节点的数量循环过程中往队列里push进下一层的节点len(q)已经变了但range(len(q))是在进入循环前计算好的所以它只遍历当前层的节点数。举个例子队列里第一层只有根节点len(q)是1for循环只跑一次处理根节点时push进两个孩子队列变成2个节点进入下一轮len(q)是2for循环跑两次把两个孩子都取出来同时push进四个孙子节点。这样每一轮都精确地处理一层不会越界。4.3 从102延伸出去的同源变体题102这道题看着简单却是一整类题目的基础。层序遍历的框架一旦熟练下面这些题你都可以用同一套核心代码改改题目改动点复杂度与本体的关系107. 二叉树的层序遍历 II每层结果从数组头部插入或最后反转res完全复用102199. 二叉树的右视图只收集每一层最后一个节点的值只改for循环内的收集逻辑637. 二叉树的层平均值每层求和再取平均只改收集逻辑429. N叉树的层序遍历遍历children而不是left/right入队逻辑换成children515. 在每个树行中找最大值记录每层最大节点值只改收集逻辑116. 填充每个节点的下一个右侧节点指针用队列做层序再连指针在层序框架上增加指针连接104. 二叉树的最大深度层序遍历的层数就是最大深度统计res的长度或单独计数111. 二叉树的最小深度第一个没有左右孩子的节点出现在哪层那层就是最小深度在遍历时提前判断叶子节点这些题目我在刷的时候最大的感受是102的代码框架就是一个“遍历引擎”引擎不动只改“每层处理逻辑”那一小块就能应对一大片题目。所以别把这题当孤立题刷要在脑子里把它当成“层序家族”的底座。5. 刷这套题时我踩过的坑和最后的建议这几道题的坑不算多但如果没人提醒确实容易在细节上浪费不少时间。我把自己踩过的、身边朋友也踩过的几个问题集中说一下。5.1 空指针错误报错信息的另一层含义很多初学者在LeetCode上提交二叉树相关的题会遇到“AttributeError: NoneType object has no attribute val”这类报错。这个报错在网络热词里被反复讨论说明它不是个例。这个错误绝大多数情况不是LeetCode的坑而是你没有处理空节点。比如层序遍历里你没判断node.left是否为空就直接node.left.val自然报错递归里base case没写全递归到None节点上还去访问val也会面对同样的错误。我的建议是每道二叉树题的代码写完后先自己检查一遍“所有取.val的地方它的对象有没有可能是None”。养成了这个习惯这类报错基本能消除90%。剩下的10%多半是题目给你的树本来就是空树记得开头补一句if not root: return []就行。5.2 二叉树的“空位”问题刷层序题的时候有人会遇到一个困惑LeetCode题目里用数组表示的二叉树比如[3,9,20,null,null,15,7]这个null是不是一个真实节点不是。层序数组里的null只是用来占位表示这个位置没有节点。但在实际代码里树的节点结构里根本不存在“值为null的节点”只有“这个引用指向None”。所以你在做层序遍历时queue里永远不会出现null占位符只会在push孩子时跳过None。如果题目要求你按照数组来还原一棵树那另当别论但LeetCode 102、144、145、94这些题输入都是已经建好的树对象不是数组别把数组的null概念带进代码逻辑里。5.3 关于刷题顺序和训练营节奏的体会代码随想录这套训练营的安排第13天集中做二叉树遍历是有意为之的。前面链表、哈希表、字符串那些题目主要锻炼的是对线性结构的处理到了二叉树思维方式要从“线性”切换到“树形”递归思想正式上场。如果前面基础没打牢这一天的题目会特别吃力。按训练营的节奏第一天先把递归遍历写熟第二天再上迭代第三天再碰层序这个梯度我个人体验下来是比较舒服的。不要第一天就想把四种遍历全部拿下大脑会把相似代码混淆起来第二天全忘干净。我个人的体会是二叉树遍历这四道题最重要的不是“能写出代码”而是“能解释为什么要这么写”。面试时候官不会只让你写前序递归他很可能会追问“不用递归怎么写”“层序用队列还是栈”“空间复杂度是多少”。所以刷的时候多问自己几个为什么比多刷一遍题更有价值。这套题真正吃透之后后面遇到二叉树的属性题、路径题、构造题你会发现自己上手快很多。祝卡在递归和迭代之间的你早日把这层窗户纸捅破。
刚开始刷二叉树的时候我一度以为自己永远记不住这三道题的代码。LeetCode 144、145、94前序遍历、后序遍历、中序遍历递归版本三分钟写完迭代版本一写就卡壳尤其是中序和后续每次对着空栈发呆总觉得逻辑在脑子里是通的落到代码上就全是问题。后来跟着代码随想录的训练营刷到第十三天把的递归遍历和迭代遍历从头到尾捋了一遍又把102题层序遍历加了进来才真正理解了“遍历顺序”这件事的本质。这篇东西就是给我的刷题笔记做个沉淀。如果你也处在“递归能写但迭代总卡”的阶段或者刚准备开始刷二叉树我尽量把每一行代码背后的为什么讲清楚。文章里有完整的解题模板、复杂度分析还有我踩过的几个坑希望能让你少走点弯路。1. 递归遍历先想清楚这三件事前中后序随便写递归版本是二叉树遍历的起点也是后边所有写法的根基。LeetCode 144、145、94三道题的递归解法本质上是在同一个模板里换三行代码的顺序所以别把三道题当成三个知识点去背当成一个知识点去理解就好。1.1 为什么空节点返回是递归的“刹车”先看最基础的递归模板拿前序遍历举例def preorderTraversal(root): if not root: return [] res [root.val] res preorderTraversal(root.left) res preorderTraversal(root.right) return res很多人刚写递归的时候第一反应是“我要用一个全局数组来收集结果”然后在递归函数里不断append。但你看上面这种写法每一层递归都返回一个列表往上层层拼接最后整棵树的结果就出来了。这个写法的好处是不需要额外定义一个成员变量函数本身就是纯函数刷题和面试的时候都不容易写出bug。这里的if not root不是可有可无的边界条件它是整个递归的“刹车”。二叉树的递归遍历本质上是在模拟一条从根节点出发、不断往下走、走到尽头再回头的过程。如果没有这辆“刹车”函数会一直往None的孩子节点里钻直到栈溢出。你可以把它理解成递归里的base case到达空节点说明这条路走到了头该掉头回去了。1.2 三序遍历其实只有一行代码的差别前序、中序、后序这三个名字描述的是“根节点”在什么时候被处理前序先处理根再处理左子树最后处理右子树简称中左右。中序先处理左子树再处理根最后处理右子树简称左中右。后序先处理左子树再处理右子树最后处理根简称左右中。把三个递归版本放在一起看区别就更明显了def preorderTraversal(root): # 中左右 if not root: return [] res [root.val] res preorderTraversal(root.left) res preorderTraversal(root.right) return res def inorderTraversal(root): # 左中右 if not root: return [] res [] res inorderTraversal(root.left) res.append(root.val) res inorderTraversal(root.right) return res def postorderTraversal(root): # 左右中 if not root: return [] res [] res postorderTraversal(root.left) res postorderTraversal(root.right) res.append(root.val) return res看到没有三份代码几乎一样区别只在于res.append(root.val)这一句的位置在最前面就是前序在中间就是中序在最后就是后序。递归遍历的核心逻辑是统一的每次处理一个节点先递归左子树再递归右子树根节点的处理顺序决定遍历顺序。这里我建议大家动手画一棵三层的二叉树比如1为根、2和3分别为左右孩子、4是2的左孩子然后分别按三种顺序在图上标注节点被“读到”的顺序。画完之后你会发现前序是“从上往下先左后右”中序是“从左往右先下后上”后序是“从下往上先左后右”。这个直观感觉比背口诀重要得多。1.3 递归的时间与空间复杂度别只记结论三道递归解法的时间复杂度都是O(n)因为每个节点恰好被访问一次。空间复杂度是O(h)h是树的高度。这个h在最坏情况下可能是n比如一棵只有左孩子的链式树递归深度就达到了n在平衡二叉树里h大约是log n。所以递归的空间复杂度不是固定的O(n)而是取决于树长什么样。很多题解直接写“空间复杂度O(n)”是为了简化描述准备的退化成链表的最坏情况。面试的时候如果被追问能说清楚“递归深度等于树高”这一层会显得你对本原理是真懂了。2. 迭代遍历一个栈怎么同时驾驭前序和中序递归能解决的问题迭代基本都能解决因为递归本身就是在隐式地使用函数调用栈。迭代遍历就是把这个栈从系统手里拿过来自己显式地维护。这也是LeetCode 144、145、94三道题里最常见的一类进阶考法不让你用递归强制你用迭代。2.1 前序的“右左入栈”为什么能保证顺序前序遍历迭代写法是三个里面最简单的def preorderTraversal(root): if not root: return [] stack [root] res [] 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关键就在最后两个if的顺序先压右孩子再压左孩子。因为栈是后进先出弹出的顺序会和压入的顺序相反。你希望弹出顺序是“先左后右”就得让右孩子先进栈、左孩子后进栈这样左孩子会被先弹出。记住一个口诀前序迭代就是“中左右入栈右左”。每一轮循环做的事情其实很单纯弹出栈顶节点并记录值然后把这个节点的右孩子、左孩子依次压入栈。栈保证了我们永远先处理左子树这一支等左子树整支处理完栈中自然剩下的就是之前压入的各个右子树节点。我第一次写这个解法时犯过一个错先压左孩子再压右孩子结果顺序变成根、右子树、左子树整棵树的顺序全乱了。后来想明白了栈的特性这个坑就再也没踩过。2.2 中序为什么要一路压左链中序迭代比前序难一个档次因为它不是简单的“弹出就处理”。看代码def inorderTraversal(root): if not root: return [] stack [] cur root res [] while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res这里最核心的是内层那个while cur循环它的作用是把当前节点到它的最左叶子这一条链路上的所有节点全部压入栈。为什么因为中序是左中右我们必须先处理一棵子树最左边的节点然后才能往回处理它的父节点。用一个生活场景来类比中序遍历就像你要从一棵树的最左下角开始一格一格往右上方扫过去。遇到每一个节点你不能立刻处理它因为它的左子树还没扫完所以你必须先把节点记在栈里继续往下钻左子树。钻到最左边没有左孩子了这时候才从栈里弹出这个最左节点处理它然后转向它的右子树重复同样的逻辑。整个过程可以概括为三句话一直往左压栈弹出并处理转向右子树。很多教程会把这套写法直接甩给你但如果你不理解“为什么要一路压栈”你很难在考场上默写出来。理解了之后每一次cur cur.right都是在说“左子树处理完了根也处理完了该轮到我这一侧的右子树了。”2.3 迭代写法的空指针雷区迭代写法的bug高发区有两个。第一个是前序里忘记判断节点是否存在。有些同学会写成if node.right: stack.append(node.right) if node.left: stack.append(node.left)漏掉if判断直接把空指针压进栈里循环里就会对None取.val直接报AttributeError。其实这道题里用if判断还是if root初始化两种风格都能过但不能夹在中间造成逻辑混乱。第二个是中序初始化时if not root: return []和cur root这两个条件缺一不可。如果没有最外层的空树判断while cur or stack在root为空时会直接跳过循环返回空数组结果其实也是对的但如果你想省掉判断得确保stack的初始状态没问题。代码风格上我建议保留明确的空树判断可读性更好面试的时候也更容易讲清楚。3. 后序遍历的取巧路径前序反转法与标记位写法后序迭代是所有二叉树遍历里最让人头大的一个。网上的主流解法至少有三种我先讲最取巧的一种再说一种我自己后来最常用的写法。3.1 前序反转为什么成立先看这段代码def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]你可以把它理解成“前序遍历的镜像版”前序是“中左右”这里先按“中右左”的顺序收集结果所以先压左孩子再压右孩子让右子树先出栈最后把整个结果数组反转就变成了“左右中”也就是后序遍历。为什么反转一下就成立了因为后序是左右中它和前序的中左右正好是镜像对称的。你按中右左的方式收集得到的结果反转过来恰好就是左右中。这个方法在面试里非常实用因为代码量跟前序几乎一样只需要改一下两个if的顺序再在最后加一个反转。反转整列表的时间复杂度是O(n)加上前面遍历的O(n)整体还是O(n)不影响大O级别。空间上多了一个res数组存结果这部分本来就是答案需要占用的空间不算额外开销。3.2 标记位写法用None统一三种遍历除了前序反转还有一种“标记位”写法也是代码随想录教程里重点推荐的路子。它的核心思路是每次把节点压入栈时同时在它后面压一个标记当这个标记被弹出时说明这个节点的左右子树已经处理完了可以输出这个节点本身了。def postorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() if node: stack.append(node) stack.append(None) # 标记表示node已经可以输出了 if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res你可能会问前序和中序是不是也能用同一种套路完全可以只需要调整节点、标记、左右孩子入栈的顺序。标记位写法的本质是用一个额外的None元素模拟递归的“函数返回”动作。递归里函数处理完一棵子树后会自动回到上一层迭代写法没有这个自动机制所以需要自己往栈里塞一个“返回点”。这种写法的好处是模板统一三种遍历只需要调整压栈顺序。坏处是代码看起来有点绕第一次看容易懵。我建议先用前序反转法把后序遍历跑通等对栈的操作足够熟悉了再来体会标记位写法的精妙。3.3 我后来为什么倾向于标记位写法说实话如果只是为了AC一道题前序反转法更短、更不容易写错。但我后来在做一些二叉树相关的综合题时发现标记位写法更接近递归的思考方式它的入栈顺序是从“最迟到处理”的逻辑倒推的只要把递归里“左、根、右/左、右、根”的访问顺序翻译成入栈顺序就行不容易陷入“中序那个while循环怎么控制”的困惑里。另外一点标记位思路对理解其他需要遍历顺序的题目也有帮助。比如二叉树最近公共祖先、二叉树展开为链表这类题目不要求纯按后序输出但需要用“先孩子后自己”的处理次序标记位写法体现出的“延迟处理”思想就很有用了。这里也提一句网上还能看到“双栈法”解决后序遍历思路是先遍历得到中右左再用另一个栈反转。原理和前序反转法完全一样我个人觉得有一个就够用了。4. 层序遍历一个队列解决的不只是102这道题LeetCode 102是一道“看起来基础、实际上能延伸出一大堆题”的典型代表。层序遍历的写法套路很固定但理解清楚它为什么用队列以及怎么控制“一层”的范围比背代码重要得多。4.1 为什么层序必须用队列先看基础代码from collections import deque def levelOrder(root): if not root: return [] q deque([root]) res [] while q: level [] for _ in range(len(q)): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res层序遍历和前中后序的最大区别是它不是深度优先而是广度优先。深度优先用栈因为要一条路走到黑再回头广度优先用队列因为要一层一层地平推。这是“用什么数据结构”的根本依据不要死记。想象一下你手头有一个队列初始时只有根节点。你把根节点从队头取出来把它左右两个孩子从队尾放进去。第二轮循环队列里的两个孩子会被依次取出同时它们各自的孩子又会被放进队尾。每一轮队列里装的恰好就是某一层的节点你从队头取走老节点从队尾放进去新节点先进先出自然保证了“同一层按从左到右的顺序输出”。4.2 用size固定每层范围初学者容易写错的地方是不知道每层有多少个节点直接把while q写成while q把所有节点一股脑输出层与层之间就混在一起了。上面代码里的for _ in range(len(q))是控制一层的边界。关键点在于进入for循环时len(q)记录的是当前层节点的数量循环过程中往队列里push进下一层的节点len(q)已经变了但range(len(q))是在进入循环前计算好的所以它只遍历当前层的节点数。举个例子队列里第一层只有根节点len(q)是1for循环只跑一次处理根节点时push进两个孩子队列变成2个节点进入下一轮len(q)是2for循环跑两次把两个孩子都取出来同时push进四个孙子节点。这样每一轮都精确地处理一层不会越界。4.3 从102延伸出去的同源变体题102这道题看着简单却是一整类题目的基础。层序遍历的框架一旦熟练下面这些题你都可以用同一套核心代码改改题目改动点复杂度与本体的关系107. 二叉树的层序遍历 II每层结果从数组头部插入或最后反转res完全复用102199. 二叉树的右视图只收集每一层最后一个节点的值只改for循环内的收集逻辑637. 二叉树的层平均值每层求和再取平均只改收集逻辑429. N叉树的层序遍历遍历children而不是left/right入队逻辑换成children515. 在每个树行中找最大值记录每层最大节点值只改收集逻辑116. 填充每个节点的下一个右侧节点指针用队列做层序再连指针在层序框架上增加指针连接104. 二叉树的最大深度层序遍历的层数就是最大深度统计res的长度或单独计数111. 二叉树的最小深度第一个没有左右孩子的节点出现在哪层那层就是最小深度在遍历时提前判断叶子节点这些题目我在刷的时候最大的感受是102的代码框架就是一个“遍历引擎”引擎不动只改“每层处理逻辑”那一小块就能应对一大片题目。所以别把这题当孤立题刷要在脑子里把它当成“层序家族”的底座。5. 刷这套题时我踩过的坑和最后的建议这几道题的坑不算多但如果没人提醒确实容易在细节上浪费不少时间。我把自己踩过的、身边朋友也踩过的几个问题集中说一下。5.1 空指针错误报错信息的另一层含义很多初学者在LeetCode上提交二叉树相关的题会遇到“AttributeError: NoneType object has no attribute val”这类报错。这个报错在网络热词里被反复讨论说明它不是个例。这个错误绝大多数情况不是LeetCode的坑而是你没有处理空节点。比如层序遍历里你没判断node.left是否为空就直接node.left.val自然报错递归里base case没写全递归到None节点上还去访问val也会面对同样的错误。我的建议是每道二叉树题的代码写完后先自己检查一遍“所有取.val的地方它的对象有没有可能是None”。养成了这个习惯这类报错基本能消除90%。剩下的10%多半是题目给你的树本来就是空树记得开头补一句if not root: return []就行。5.2 二叉树的“空位”问题刷层序题的时候有人会遇到一个困惑LeetCode题目里用数组表示的二叉树比如[3,9,20,null,null,15,7]这个null是不是一个真实节点不是。层序数组里的null只是用来占位表示这个位置没有节点。但在实际代码里树的节点结构里根本不存在“值为null的节点”只有“这个引用指向None”。所以你在做层序遍历时queue里永远不会出现null占位符只会在push孩子时跳过None。如果题目要求你按照数组来还原一棵树那另当别论但LeetCode 102、144、145、94这些题输入都是已经建好的树对象不是数组别把数组的null概念带进代码逻辑里。5.3 关于刷题顺序和训练营节奏的体会代码随想录这套训练营的安排第13天集中做二叉树遍历是有意为之的。前面链表、哈希表、字符串那些题目主要锻炼的是对线性结构的处理到了二叉树思维方式要从“线性”切换到“树形”递归思想正式上场。如果前面基础没打牢这一天的题目会特别吃力。按训练营的节奏第一天先把递归遍历写熟第二天再上迭代第三天再碰层序这个梯度我个人体验下来是比较舒服的。不要第一天就想把四种遍历全部拿下大脑会把相似代码混淆起来第二天全忘干净。我个人的体会是二叉树遍历这四道题最重要的不是“能写出代码”而是“能解释为什么要这么写”。面试时候官不会只让你写前序递归他很可能会追问“不用递归怎么写”“层序用队列还是栈”“空间复杂度是多少”。所以刷的时候多问自己几个为什么比多刷一遍题更有价值。这套题真正吃透之后后面遇到二叉树的属性题、路径题、构造题你会发现自己上手快很多。祝卡在递归和迭代之间的你早日把这层窗户纸捅破。
