1. 二叉树基础与遍历顺序第十四天的知识地基算法训练营走到第十四天主题从数组、链表、哈希表一下子跳到二叉树任务量明显上了一个台阶。这一天的标题包含的内容非常多二叉树理论基础、递归遍历、迭代遍历、统一迭代遍历、层序遍历再加两道最近公共祖先的经典题。第一次看到这个安排的时候我心里是有点慌的因为前十天内容基本都是线性结构突然转二叉树既要理解树的定义和遍历顺序又要同时消化递归和迭代两套写法后面还有236、235这种思考量很大的题一天之内全部掌握并不容易。但我现在回头看这个安排其实非常紧凑且合理。二叉树的题目有一个共性只要遍历逻辑真正吃透了绝大多数题都能靠同一套思想打底第八天的调度题、第十天的回溯题反而没有这么强的统一性。这篇文章是我训练营第十四天之后的复盘整理把当天涉及的知识点逐一拆开讲包括为什么这么写、跑代码时会踩什么坑、面试时哪些细节容易被追问。适合正在刷二叉树专题的朋友也适合面试前想快速回顾遍历和公共祖先解法的人。下面统一用Python演示思路对C、Java、Go完全一致。1.1 先分清这几类二叉树后面才不会混二叉树这个概念本身很简单每个节点最多有两个孩子。真正容易让人迷糊的是满二叉树、完全二叉树、二叉搜索树、平衡二叉树这几个名词因为很多题解在解释的时候会默认你已经知道它们的区别。满二叉树指每一层都是满的节点个数是2的k次方减1完全二叉树是除了最后一层其他层都是满的最后一层从左到右连续排列。这两个定义在很多层序遍历题目里会用到因为完全二叉树可以用数组下标来定位孩子节点。二叉搜索树BST是刷题出现频率最高的特殊二叉树它满足左子树所有节点值都小于根节点右子树所有节点值都大于根节点并且中序遍历结果是递增序列。这个特性在后面做235题时会成为解题的关键。平衡二叉树则是左右子树高度差不超过1。这里我想特别强调刷题时不需要分得那么细但看到题目里写明“二叉搜索树”或“平衡二叉树”时就要意识到这五个字本身就是条件解法往往要围绕它展开而不是只当成一棵普通二叉树。1.2 前中后序遍历到底差在哪前序、中序、后序这三个名称看着绕其实只需要记住一句话它们描述的是中间节点被访问的位置。前序是先访问中间节点再访问左子树最后访问右子树写作中左右中序是先左子树、再中间节点、最后右子树写作左中右后序是先左子树、再右子树、最后中间节点写作左右中。所谓的“前中后”指的是中间节点在整体顺序里的前后位置而左子树永远优先于右子树。这个区分看起来是基础中的基础却是整天的核心。递归遍历、迭代遍历、统一迭代遍历本质上就是在用不同的方式实现这三种顺序。尤其要注意后序遍历因为后序是天然的自底向上过程先处理完左右子树再来处理当前节点这种特性在最近公共祖先题目中非常重要。我一开始总把中序和后序搞混后来每次看题都先在纸上写出访问顺序再动手写代码会清晰很多。1.3 Python里如何定义二叉树节点Python没有内置的二叉树结构需要自己定义TreeNode类。训练营里用的通常是下面这种结构class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right节点的值、左孩子、右孩子都通过初始化参数传入。很多初学者会忽略一个问题LeetCode上给的测试用例是数组形式比如[3,9,20,null,null,15,7]但这只是层序遍历的输入表示真正运行时会先构建成一棵二叉树再传入根节点。所以刷题时不要纠结如何直接把数组变成树要记住自己面对的是一个根节点对象后续所有操作都是围绕root展开的。另外还要注意空节点的表示。在Python里用None表示没有左孩子或右孩子写递归的时候必须先判断当前节点是否为None这是几乎所有二叉树题目共同的终止条件。漏掉空节点判断往往是递归栈溢出或属性访问报错的直接原因。2. 递归遍历三要素写法和刷题最容易翻车的几个点递归是二叉树遍历中最直观的写法也是后面统一迭代遍历、最近公共祖先题目的思考基础。如果你之前写递归总是靠“感觉”那第十四天正好是一个把递归彻底搞懂的契机。二叉树的递归遍历可以提炼成非常固定的三步而且这三步适用于几乎所有递归题目不只是树的遍历。2.1 递归三要素参数、终止条件、单层逻辑写递归前先问自己三个问题。第一这个函数需要什么参数需要返回什么。第二什么时候递归可以停止也就是终止条件是什么。第三在每一层递归里只处理当前节点和它的左右子树具体做什么操作。拿前序遍历举例。参数只需要当前节点node因为我们要把节点值收集到一个结果列表里所以返回值可以设计成None直接在外部结果列表里追加值终止条件就是当前节点为空时直接返回None单层逻辑则是先记录当前节点值再递归左子树最后递归右子树。把这三步写清楚代码基本不会跑偏。def preorder_traversal(root): result [] def dfs(node): if node is None: return result.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return result这里我用了一个嵌套函数dfs来遍历result定义在外层也就是通过闭包来收集结果。使用嵌套函数的好处是不需要额外维护一个全局变量也不会因为多次调用函数导致结果列表累积。2.2 中序和后序递归只需要调换三行位置前序递归一旦会写中序和后序几乎不需要重新理解只要改变处理节点值的位置。中序是先递归左子树、记录值、再递归右子树后序是先递归左子树、再递归右子树、最后记录值。三种写法放在一起对比你会发现代码结构一模一样只有result.append(node.val)这一行的位置不同。def inorder_traversal(root): result [] def dfs(node): if node is None: return dfs(node.left) result.append(node.val) dfs(node.right) dfs(root) return result def postorder_traversal(root): result [] def dfs(node): if node is None: return dfs(node.left) dfs(node.right) result.append(node.val) dfs(root) return result理解了这一点之后你会突然发现递归遍历不是一个需要死记硬背的东西。每次写题前先确定中间节点要放在哪一步处理再套用这个框架即可。2.3 递归中容易踩的坑返回值、闭包和内存第一个坑在LeetCode环境里函数会被多次调用如果把result定义成函数外的全局变量第二次调用时上次的残留数据就会被带进来。我一开始就在本地训练时踩过这个坑界面上每次用例的结果都包含上一轮的数据。解决办法就是像上面一样把result定义在函数内部并利用嵌套函数做递归。第二个坑递归函数没有返回值。有些题需要递归结果往上传递比如后面要讲的最近公共祖先如果只是简单地在递归里修改外部列表考虑返回值的方式就要重写。递归遍历相对简单但你要养成“思考返回值该怎么设计”的习惯否则到236题时会卡住。第三个坑递归深度。Python默认的递归深度大约在1000层左右如果二叉树在最坏情况下退化成一个链表比如每个节点只有左孩子递归遍历就可能超出限制。实际面试时一般不会出现极端的链表式二叉树但日常测试时要注意不要因为这种特殊情况怀疑自己的递归代码写错了。3. 迭代遍历用栈模拟函数调用栈中序为何不能照搬前序递归之所以能自动完成回溯是因为系统会为每次函数调用分配一个栈帧。用迭代实现遍历本质就是自己维护一个栈手动模拟这个过程。前序和后序相对直观中序则是很多人第一次卡住的地方。3.1 前序迭代先处理根再按右左顺序入栈前序遍历的顺序是中左右也就是先访问中间节点再访问左子树最后访问右子树。用栈实现时我们先让根节点入栈然后循环弹出栈顶节点并记录值紧接着把右孩子入栈、再把左孩子入栈。为什么右孩子先入栈因为栈是后进先出的结构我们希望左孩子先被处理所以就要让左孩子后入栈这样它才会在栈顶。def preorder_traversal(root): if not root: return [] stack [root] result [] 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.2 后序迭代借用前序结果再反转后序遍历和前序遍历存在一个非常有意思的联系。前序结果是中左右如果我在前序迭代里把入栈顺序改成先左后右那么结果会变成中右左。中右左做一次反转就得到了左右中也就是后序。这个思路代码实现非常短不少题解都推荐这种偷懒写法。def postorder_traversal(root): if not root: return [] stack [root] result [] while stack: node stack.pop() result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1]使用[::-1]反转列表是Python里最简单的方式。如果你使用C可以最后对记录结果reverse一下。这种写法的优点是代码量少、不容易出错缺点是需要额外进行一次反转性能上通常可以接受。3.3 中序迭代为什么不能只调整前序的三行中序迭代和前序迭代没有表面上看起来那么简单它的核心区别在于前序可以在弹出节点时立刻访问因为中间节点最开始就要处理而中序必须先把当前节点的所有左子树走完才能访问当前节点。所以在中序迭代里我们要用一个指针不断往左走沿途把节点压入栈直到左子树为空再弹出栈顶节点访问然后将指针转向右子树。def inorder_traversal(root): result [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result这里有个容易搞混的地方外层循环条件是cur or stack而不是单纯的while stack。因为刚开始时栈是空的但cur指向根节点必须进入循环后来当栈空并且cur也变为空时整棵树才遍历完毕。3.4 访问顺序和处理顺序的分离前序迭代里“访问”和“处理”是同步的弹出节点就记录值中序迭代里访问和处理被分开了节点先进栈入栈但不立即记录等到左子树处理完才弹出来记录。这个“访问与处理分离”的思路非常重要因为它直接催生了第四部分的统一迭代遍历。我给一个直接的比喻递归像是一个自动记账系统你把任务交给系统系统自己用调用栈记账迭代遍历则是你亲自记账每一步都清楚当前栈里保存了什么。后者代码看起来不那么优雅但理解了它你对递归原理的掌控度会明显提升。4. 统一迭代遍历一种标记法让三种顺序共用同一套代码讲完中序迭代之后训练营里有一个很自然的疑问前序、后序、中序的迭代代码长得都不一样每次写都要重新推导有没有一套模板能够统一处理答案是有的思路就是给栈里的每个节点加一个标记表示“这个节点已经被访问过了下次弹出时直接处理”。4.1 标记法原理用None节点做分隔统一迭代的核心做法是每次把当前节点压入栈时紧接着压入一个None作为标记。当循环弹出栈顶元素发现是None时说明下一步要弹出的节点已经访问过左右子树此时应该真正处理该节点的值。也就是说None像一道护栏把“待处理的节点”和“等下一次真正读取的节点”区分开。def preorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: if node.right: stack.append(node.right) if node.left: stack.append(node.left) stack.append(node) stack.append(None) else: node stack.pop() result.append(node.val) return result为什么前序里要先压入右孩子、再压入左孩子因为栈是后进先出我们希望处理顺序是左孩子先于右孩子那么右孩子先压入左孩子后压入。然后在左孩子之前还需要压入当前节点和None标记这样弹出顺序才是正确的“中左右”。4.2 统一模板在中序和后序里的变化模板一旦固定中序和后序只需要改变“在什么顺序下压入当前节点与标记”。前序是中左右所以入栈顺序按反方向写依次为右、左、中、None。中序是左中右入栈顺序逆序写先放右孩子、再放当前节点、再放None、最后放左孩子。后序是左右中逆序入栈顺序则是先放当前节点、再放None、再放右孩子、再放左孩子。def inorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: if node.right: stack.append(node.right) stack.append(node) stack.append(None) if node.left: stack.append(node.left) else: node stack.pop() result.append(node.val) return result def postorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: stack.append(node) stack.append(None) if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: node stack.pop() result.append(node.val) return result这套模板的优点是记忆负担小。你只需要记住“处理节点时把当前节点和None按逆序穿插进栈”另外在None弹出后处理值即可。它避免了中序迭代里“不断向左走再回头访问”的特殊逻辑把三种遍历拉到了同一个抽象层次。4.3 标记法的取舍不是所有场景都适合不过我也得说点实在的统一迭代虽然模板统一但并不是高频刷题时的首选。首先每个节点除了要额外压入一次None代码里还多了很多if node.right、if node.left的判断运行时间比递归和前序迭代稍慢。其次面试时如果一上来就写带None标记的代码容易在没有提示的情况下显得步骤跳跃别人还需要额外理解你的“标记”设计。我自己的建议是递归遍历是必须熟练的日常刷题优先用递归前序和后序迭代可以作为锻炼栈思维的练习统一迭代的价值在于帮你彻底理解访问与处理的关系同时在一些限制使用递归的笔试场景中作为备选方案。工具多一套从来不是坏事但要明确每个工具适合的场合。5. 层序遍历队列加size快照一口气看透逐层处理的套路层序遍历和前中后序遍历的思考方式完全不同。前中后序可以用深度优先的思路理解沿着一条路走到黑再回头层序则是典型的广度优先从上到下、从左到右按层推进。实现层序遍历的天然数据结构是队列因为队列先进先出正好匹配“先入队的节点先被处理”的层级顺序。5.1 为什么层序必须用队列想象排队买票先来的人先买到票离开后来的人依次接上这就是队列的行为。层序遍历时我们先把根节点入队然后循环从队列头部取出节点记录值再把它的左孩子和右孩子依次入队。这样每一次从队头取出的节点都是当前层级中尚未处理的节点而且两个孩子入队后会排在当前层所有节点的后面从而保证下一层的处理顺序。5.2 用size快照区分每一层如果只是单纯入队出队最终结果只能得到一股脑的遍历序列没法知道哪些节点属于同一层。因为队列里会同时存在当前层和下一层的节点。解决办法非常简单在进入每一层之前先记录当前队列的长度size然后只从队列里取出size个节点。这一步相当于给这一层画了一条时间线之后新入队的节点全部属于下一层不会混进这一层的循环里。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: size len(queue) level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return resultsize这个值必须在循环一开始就取好而不是在循环内部动态读取len(queue)。原因很简单在处理这一层节点的过程中我们会不断加入下一层的节点队列长度一直在变只有提前快照才能保证循环次数是当前层的节点数量。这个细节非常关键很多层序变体题都依赖这一行。5.3 层序还能解决哪些变体层序的框架一旦掌握可以一口气解决好几道题自底向上的层序遍历只需要最后把result反转二叉树右视图只需要在每一层记录最后一个节点每层最大值用max(level)直接得出锯齿形层序遍历根据当前层是奇数还是偶数决定是否反转levelN叉树的层序遍历只需要循环访问节点的多个孩子。可以说你花一小时吃透层序模板等于同时预习了很多道层序变体的面试题性价比非常高。6. 最近公共祖先236的一般二叉树解法与235的二叉搜索树捷径最后重头戏是两道最近公共祖先题目。236题针对普通二叉树必须完整遍历思考难度较高235题针对二叉搜索树可以充分利用有序性代码会短很多。把这两题放在同一天目的显然是让你体会同一个问题在不同数据结构上的解法差异。6.1 先理解公共祖先的定义给定一棵二叉树和两个节点p、q它们的最近公共祖先指的是离它们最近的、同时是p和q祖先的那个节点。注意祖先的定义包含节点自身也就是说一个节点可以是它自己的祖先。举个例子如果p是根节点的左孩子q是p的左孩子那么p就是p和q的最近公共祖先。很多人第一反应是“从根往下找分叉点”这个思路方向上没有问题但具体实现容易走偏。普通二叉树没有有序性无法通过比较大小来决定往左走还是往右走必须实际搜索整棵树并且找到p和q分别所在的位置。6.2 236题后序递归回溯为什么是通用解要同时判断p和q的位置最合适的遍历顺序是后序。因为后序是先处理完左右子树再处理当前节点天然实现了自底向上的搜索当递归函数从底层返回时我们实际上是在判断当前节点的左子树里有没有p或q右子树里有没有p或q。如果左右两边都找到了那当前节点就是它们的最近公共祖先。def lowest_common_ancestor(root, p, q): if root is None or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right这段代码的判断逻辑值得仔细读。终止条件是当前节点为空、或等于p、或等于q。递归搜索左右子树后如果left和right都不为空说明p和q分别出现在当前节点的两个子树中当前节点就是公共祖先如果只有一边不为空比如left有结果而right为空说明p和q都在左子树里直接返回左子树的结果即可。这个“把结果不断向上传递”的过程是整道题的核心。我第一次做这道题时总想用一个全局变量来记录答案结果代码越写越乱。实际上236题的递归返回值本身就是答案候选完全不需要额外存储。想通这一点代码就变得非常干净。6.3 235题BST有序性带来的快速剪枝来到235题二叉搜索树的特性要让解法完全不同。BST里任意节点的左子树所有值都小于它右子树所有值都大于它。因此从根节点开始走如果当前节点值大于p和q的值那么公共祖先一定在当前节点的左子树里如果当前节点值小于p和q的值那么公共祖先一定在右子树里如果当前节点值介于p和q之间说明p和q分布在当前节点两侧当前节点就是最近公共祖先。def lowest_common_ancestor(root, p, q): cur root while cur: if cur.val p.val and cur.val q.val: cur cur.left elif cur.val p.val and cur.val q.val: cur cur.right else: return cur return None这个迭代写法每次只向一个方向移动平均时间复杂度是O(log n)最坏情况下也是O(height)。相比236题必须完整遍历整棵树235题的剪枝思想非常直观。递归版本也完全可以代码结构只是把cur的移动换成了递归调用。6.4 两道题一起练的深意与常见误区放在同一天做这两题最大的收获应该是“识别题目类型”。很多人在236题里套用BST的剪枝思路结果发现普通二叉树左右子树大小没有规律直接走错了方向也有人做235题时非要递归遍历完整棵树虽然也能得到正确答案但白白浪费了BST的优势。我建议做题时先问自己一句这个数据结构有没有额外的有序性可以利用如果有就要停下来想一想能不能把搜索范围缩小。另一个常见误区是混淆“p或q在祖先路径”与“p或q本身”。因为祖先包含自身所以当某个节点本身就是p或q时它自己就可以作为公共祖先的候选。236题代码里那个root p or root q的终止条件就是在处理这种情况绝对不能删掉。最后说一个我自己的实践体会。训练营第十四天的内容多但内部逻辑其实是环环相扣的二叉树的概念支持遍历递归遍历支持迭代遍历统一迭代又反过来深化对递归和迭代的理解层序遍历提供了另一套处理树的方式而最近公共祖先题目正好把所有遍历知识综合起来。我后来再刷二叉树相关题目时只要看到题目要求“从下往上找”“判断两个节点是否在两侧”就会下意识先想后序遍历能不能解决。这个习惯就是从这两道公共祖先题里养出来的非常值得。
1. 二叉树基础与遍历顺序第十四天的知识地基算法训练营走到第十四天主题从数组、链表、哈希表一下子跳到二叉树任务量明显上了一个台阶。这一天的标题包含的内容非常多二叉树理论基础、递归遍历、迭代遍历、统一迭代遍历、层序遍历再加两道最近公共祖先的经典题。第一次看到这个安排的时候我心里是有点慌的因为前十天内容基本都是线性结构突然转二叉树既要理解树的定义和遍历顺序又要同时消化递归和迭代两套写法后面还有236、235这种思考量很大的题一天之内全部掌握并不容易。但我现在回头看这个安排其实非常紧凑且合理。二叉树的题目有一个共性只要遍历逻辑真正吃透了绝大多数题都能靠同一套思想打底第八天的调度题、第十天的回溯题反而没有这么强的统一性。这篇文章是我训练营第十四天之后的复盘整理把当天涉及的知识点逐一拆开讲包括为什么这么写、跑代码时会踩什么坑、面试时哪些细节容易被追问。适合正在刷二叉树专题的朋友也适合面试前想快速回顾遍历和公共祖先解法的人。下面统一用Python演示思路对C、Java、Go完全一致。1.1 先分清这几类二叉树后面才不会混二叉树这个概念本身很简单每个节点最多有两个孩子。真正容易让人迷糊的是满二叉树、完全二叉树、二叉搜索树、平衡二叉树这几个名词因为很多题解在解释的时候会默认你已经知道它们的区别。满二叉树指每一层都是满的节点个数是2的k次方减1完全二叉树是除了最后一层其他层都是满的最后一层从左到右连续排列。这两个定义在很多层序遍历题目里会用到因为完全二叉树可以用数组下标来定位孩子节点。二叉搜索树BST是刷题出现频率最高的特殊二叉树它满足左子树所有节点值都小于根节点右子树所有节点值都大于根节点并且中序遍历结果是递增序列。这个特性在后面做235题时会成为解题的关键。平衡二叉树则是左右子树高度差不超过1。这里我想特别强调刷题时不需要分得那么细但看到题目里写明“二叉搜索树”或“平衡二叉树”时就要意识到这五个字本身就是条件解法往往要围绕它展开而不是只当成一棵普通二叉树。1.2 前中后序遍历到底差在哪前序、中序、后序这三个名称看着绕其实只需要记住一句话它们描述的是中间节点被访问的位置。前序是先访问中间节点再访问左子树最后访问右子树写作中左右中序是先左子树、再中间节点、最后右子树写作左中右后序是先左子树、再右子树、最后中间节点写作左右中。所谓的“前中后”指的是中间节点在整体顺序里的前后位置而左子树永远优先于右子树。这个区分看起来是基础中的基础却是整天的核心。递归遍历、迭代遍历、统一迭代遍历本质上就是在用不同的方式实现这三种顺序。尤其要注意后序遍历因为后序是天然的自底向上过程先处理完左右子树再来处理当前节点这种特性在最近公共祖先题目中非常重要。我一开始总把中序和后序搞混后来每次看题都先在纸上写出访问顺序再动手写代码会清晰很多。1.3 Python里如何定义二叉树节点Python没有内置的二叉树结构需要自己定义TreeNode类。训练营里用的通常是下面这种结构class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right节点的值、左孩子、右孩子都通过初始化参数传入。很多初学者会忽略一个问题LeetCode上给的测试用例是数组形式比如[3,9,20,null,null,15,7]但这只是层序遍历的输入表示真正运行时会先构建成一棵二叉树再传入根节点。所以刷题时不要纠结如何直接把数组变成树要记住自己面对的是一个根节点对象后续所有操作都是围绕root展开的。另外还要注意空节点的表示。在Python里用None表示没有左孩子或右孩子写递归的时候必须先判断当前节点是否为None这是几乎所有二叉树题目共同的终止条件。漏掉空节点判断往往是递归栈溢出或属性访问报错的直接原因。2. 递归遍历三要素写法和刷题最容易翻车的几个点递归是二叉树遍历中最直观的写法也是后面统一迭代遍历、最近公共祖先题目的思考基础。如果你之前写递归总是靠“感觉”那第十四天正好是一个把递归彻底搞懂的契机。二叉树的递归遍历可以提炼成非常固定的三步而且这三步适用于几乎所有递归题目不只是树的遍历。2.1 递归三要素参数、终止条件、单层逻辑写递归前先问自己三个问题。第一这个函数需要什么参数需要返回什么。第二什么时候递归可以停止也就是终止条件是什么。第三在每一层递归里只处理当前节点和它的左右子树具体做什么操作。拿前序遍历举例。参数只需要当前节点node因为我们要把节点值收集到一个结果列表里所以返回值可以设计成None直接在外部结果列表里追加值终止条件就是当前节点为空时直接返回None单层逻辑则是先记录当前节点值再递归左子树最后递归右子树。把这三步写清楚代码基本不会跑偏。def preorder_traversal(root): result [] def dfs(node): if node is None: return result.append(node.val) dfs(node.left) dfs(node.right) dfs(root) return result这里我用了一个嵌套函数dfs来遍历result定义在外层也就是通过闭包来收集结果。使用嵌套函数的好处是不需要额外维护一个全局变量也不会因为多次调用函数导致结果列表累积。2.2 中序和后序递归只需要调换三行位置前序递归一旦会写中序和后序几乎不需要重新理解只要改变处理节点值的位置。中序是先递归左子树、记录值、再递归右子树后序是先递归左子树、再递归右子树、最后记录值。三种写法放在一起对比你会发现代码结构一模一样只有result.append(node.val)这一行的位置不同。def inorder_traversal(root): result [] def dfs(node): if node is None: return dfs(node.left) result.append(node.val) dfs(node.right) dfs(root) return result def postorder_traversal(root): result [] def dfs(node): if node is None: return dfs(node.left) dfs(node.right) result.append(node.val) dfs(root) return result理解了这一点之后你会突然发现递归遍历不是一个需要死记硬背的东西。每次写题前先确定中间节点要放在哪一步处理再套用这个框架即可。2.3 递归中容易踩的坑返回值、闭包和内存第一个坑在LeetCode环境里函数会被多次调用如果把result定义成函数外的全局变量第二次调用时上次的残留数据就会被带进来。我一开始就在本地训练时踩过这个坑界面上每次用例的结果都包含上一轮的数据。解决办法就是像上面一样把result定义在函数内部并利用嵌套函数做递归。第二个坑递归函数没有返回值。有些题需要递归结果往上传递比如后面要讲的最近公共祖先如果只是简单地在递归里修改外部列表考虑返回值的方式就要重写。递归遍历相对简单但你要养成“思考返回值该怎么设计”的习惯否则到236题时会卡住。第三个坑递归深度。Python默认的递归深度大约在1000层左右如果二叉树在最坏情况下退化成一个链表比如每个节点只有左孩子递归遍历就可能超出限制。实际面试时一般不会出现极端的链表式二叉树但日常测试时要注意不要因为这种特殊情况怀疑自己的递归代码写错了。3. 迭代遍历用栈模拟函数调用栈中序为何不能照搬前序递归之所以能自动完成回溯是因为系统会为每次函数调用分配一个栈帧。用迭代实现遍历本质就是自己维护一个栈手动模拟这个过程。前序和后序相对直观中序则是很多人第一次卡住的地方。3.1 前序迭代先处理根再按右左顺序入栈前序遍历的顺序是中左右也就是先访问中间节点再访问左子树最后访问右子树。用栈实现时我们先让根节点入栈然后循环弹出栈顶节点并记录值紧接着把右孩子入栈、再把左孩子入栈。为什么右孩子先入栈因为栈是后进先出的结构我们希望左孩子先被处理所以就要让左孩子后入栈这样它才会在栈顶。def preorder_traversal(root): if not root: return [] stack [root] result [] 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.2 后序迭代借用前序结果再反转后序遍历和前序遍历存在一个非常有意思的联系。前序结果是中左右如果我在前序迭代里把入栈顺序改成先左后右那么结果会变成中右左。中右左做一次反转就得到了左右中也就是后序。这个思路代码实现非常短不少题解都推荐这种偷懒写法。def postorder_traversal(root): if not root: return [] stack [root] result [] while stack: node stack.pop() result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1]使用[::-1]反转列表是Python里最简单的方式。如果你使用C可以最后对记录结果reverse一下。这种写法的优点是代码量少、不容易出错缺点是需要额外进行一次反转性能上通常可以接受。3.3 中序迭代为什么不能只调整前序的三行中序迭代和前序迭代没有表面上看起来那么简单它的核心区别在于前序可以在弹出节点时立刻访问因为中间节点最开始就要处理而中序必须先把当前节点的所有左子树走完才能访问当前节点。所以在中序迭代里我们要用一个指针不断往左走沿途把节点压入栈直到左子树为空再弹出栈顶节点访问然后将指针转向右子树。def inorder_traversal(root): result [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result这里有个容易搞混的地方外层循环条件是cur or stack而不是单纯的while stack。因为刚开始时栈是空的但cur指向根节点必须进入循环后来当栈空并且cur也变为空时整棵树才遍历完毕。3.4 访问顺序和处理顺序的分离前序迭代里“访问”和“处理”是同步的弹出节点就记录值中序迭代里访问和处理被分开了节点先进栈入栈但不立即记录等到左子树处理完才弹出来记录。这个“访问与处理分离”的思路非常重要因为它直接催生了第四部分的统一迭代遍历。我给一个直接的比喻递归像是一个自动记账系统你把任务交给系统系统自己用调用栈记账迭代遍历则是你亲自记账每一步都清楚当前栈里保存了什么。后者代码看起来不那么优雅但理解了它你对递归原理的掌控度会明显提升。4. 统一迭代遍历一种标记法让三种顺序共用同一套代码讲完中序迭代之后训练营里有一个很自然的疑问前序、后序、中序的迭代代码长得都不一样每次写都要重新推导有没有一套模板能够统一处理答案是有的思路就是给栈里的每个节点加一个标记表示“这个节点已经被访问过了下次弹出时直接处理”。4.1 标记法原理用None节点做分隔统一迭代的核心做法是每次把当前节点压入栈时紧接着压入一个None作为标记。当循环弹出栈顶元素发现是None时说明下一步要弹出的节点已经访问过左右子树此时应该真正处理该节点的值。也就是说None像一道护栏把“待处理的节点”和“等下一次真正读取的节点”区分开。def preorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: if node.right: stack.append(node.right) if node.left: stack.append(node.left) stack.append(node) stack.append(None) else: node stack.pop() result.append(node.val) return result为什么前序里要先压入右孩子、再压入左孩子因为栈是后进先出我们希望处理顺序是左孩子先于右孩子那么右孩子先压入左孩子后压入。然后在左孩子之前还需要压入当前节点和None标记这样弹出顺序才是正确的“中左右”。4.2 统一模板在中序和后序里的变化模板一旦固定中序和后序只需要改变“在什么顺序下压入当前节点与标记”。前序是中左右所以入栈顺序按反方向写依次为右、左、中、None。中序是左中右入栈顺序逆序写先放右孩子、再放当前节点、再放None、最后放左孩子。后序是左右中逆序入栈顺序则是先放当前节点、再放None、再放右孩子、再放左孩子。def inorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: if node.right: stack.append(node.right) stack.append(node) stack.append(None) if node.left: stack.append(node.left) else: node stack.pop() result.append(node.val) return result def postorder_traversal(root): result [] stack [root] if root else [] while stack: node stack.pop() if node is not None: stack.append(node) stack.append(None) if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: node stack.pop() result.append(node.val) return result这套模板的优点是记忆负担小。你只需要记住“处理节点时把当前节点和None按逆序穿插进栈”另外在None弹出后处理值即可。它避免了中序迭代里“不断向左走再回头访问”的特殊逻辑把三种遍历拉到了同一个抽象层次。4.3 标记法的取舍不是所有场景都适合不过我也得说点实在的统一迭代虽然模板统一但并不是高频刷题时的首选。首先每个节点除了要额外压入一次None代码里还多了很多if node.right、if node.left的判断运行时间比递归和前序迭代稍慢。其次面试时如果一上来就写带None标记的代码容易在没有提示的情况下显得步骤跳跃别人还需要额外理解你的“标记”设计。我自己的建议是递归遍历是必须熟练的日常刷题优先用递归前序和后序迭代可以作为锻炼栈思维的练习统一迭代的价值在于帮你彻底理解访问与处理的关系同时在一些限制使用递归的笔试场景中作为备选方案。工具多一套从来不是坏事但要明确每个工具适合的场合。5. 层序遍历队列加size快照一口气看透逐层处理的套路层序遍历和前中后序遍历的思考方式完全不同。前中后序可以用深度优先的思路理解沿着一条路走到黑再回头层序则是典型的广度优先从上到下、从左到右按层推进。实现层序遍历的天然数据结构是队列因为队列先进先出正好匹配“先入队的节点先被处理”的层级顺序。5.1 为什么层序必须用队列想象排队买票先来的人先买到票离开后来的人依次接上这就是队列的行为。层序遍历时我们先把根节点入队然后循环从队列头部取出节点记录值再把它的左孩子和右孩子依次入队。这样每一次从队头取出的节点都是当前层级中尚未处理的节点而且两个孩子入队后会排在当前层所有节点的后面从而保证下一层的处理顺序。5.2 用size快照区分每一层如果只是单纯入队出队最终结果只能得到一股脑的遍历序列没法知道哪些节点属于同一层。因为队列里会同时存在当前层和下一层的节点。解决办法非常简单在进入每一层之前先记录当前队列的长度size然后只从队列里取出size个节点。这一步相当于给这一层画了一条时间线之后新入队的节点全部属于下一层不会混进这一层的循环里。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: size len(queue) level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return resultsize这个值必须在循环一开始就取好而不是在循环内部动态读取len(queue)。原因很简单在处理这一层节点的过程中我们会不断加入下一层的节点队列长度一直在变只有提前快照才能保证循环次数是当前层的节点数量。这个细节非常关键很多层序变体题都依赖这一行。5.3 层序还能解决哪些变体层序的框架一旦掌握可以一口气解决好几道题自底向上的层序遍历只需要最后把result反转二叉树右视图只需要在每一层记录最后一个节点每层最大值用max(level)直接得出锯齿形层序遍历根据当前层是奇数还是偶数决定是否反转levelN叉树的层序遍历只需要循环访问节点的多个孩子。可以说你花一小时吃透层序模板等于同时预习了很多道层序变体的面试题性价比非常高。6. 最近公共祖先236的一般二叉树解法与235的二叉搜索树捷径最后重头戏是两道最近公共祖先题目。236题针对普通二叉树必须完整遍历思考难度较高235题针对二叉搜索树可以充分利用有序性代码会短很多。把这两题放在同一天目的显然是让你体会同一个问题在不同数据结构上的解法差异。6.1 先理解公共祖先的定义给定一棵二叉树和两个节点p、q它们的最近公共祖先指的是离它们最近的、同时是p和q祖先的那个节点。注意祖先的定义包含节点自身也就是说一个节点可以是它自己的祖先。举个例子如果p是根节点的左孩子q是p的左孩子那么p就是p和q的最近公共祖先。很多人第一反应是“从根往下找分叉点”这个思路方向上没有问题但具体实现容易走偏。普通二叉树没有有序性无法通过比较大小来决定往左走还是往右走必须实际搜索整棵树并且找到p和q分别所在的位置。6.2 236题后序递归回溯为什么是通用解要同时判断p和q的位置最合适的遍历顺序是后序。因为后序是先处理完左右子树再处理当前节点天然实现了自底向上的搜索当递归函数从底层返回时我们实际上是在判断当前节点的左子树里有没有p或q右子树里有没有p或q。如果左右两边都找到了那当前节点就是它们的最近公共祖先。def lowest_common_ancestor(root, p, q): if root is None or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right这段代码的判断逻辑值得仔细读。终止条件是当前节点为空、或等于p、或等于q。递归搜索左右子树后如果left和right都不为空说明p和q分别出现在当前节点的两个子树中当前节点就是公共祖先如果只有一边不为空比如left有结果而right为空说明p和q都在左子树里直接返回左子树的结果即可。这个“把结果不断向上传递”的过程是整道题的核心。我第一次做这道题时总想用一个全局变量来记录答案结果代码越写越乱。实际上236题的递归返回值本身就是答案候选完全不需要额外存储。想通这一点代码就变得非常干净。6.3 235题BST有序性带来的快速剪枝来到235题二叉搜索树的特性要让解法完全不同。BST里任意节点的左子树所有值都小于它右子树所有值都大于它。因此从根节点开始走如果当前节点值大于p和q的值那么公共祖先一定在当前节点的左子树里如果当前节点值小于p和q的值那么公共祖先一定在右子树里如果当前节点值介于p和q之间说明p和q分布在当前节点两侧当前节点就是最近公共祖先。def lowest_common_ancestor(root, p, q): cur root while cur: if cur.val p.val and cur.val q.val: cur cur.left elif cur.val p.val and cur.val q.val: cur cur.right else: return cur return None这个迭代写法每次只向一个方向移动平均时间复杂度是O(log n)最坏情况下也是O(height)。相比236题必须完整遍历整棵树235题的剪枝思想非常直观。递归版本也完全可以代码结构只是把cur的移动换成了递归调用。6.4 两道题一起练的深意与常见误区放在同一天做这两题最大的收获应该是“识别题目类型”。很多人在236题里套用BST的剪枝思路结果发现普通二叉树左右子树大小没有规律直接走错了方向也有人做235题时非要递归遍历完整棵树虽然也能得到正确答案但白白浪费了BST的优势。我建议做题时先问自己一句这个数据结构有没有额外的有序性可以利用如果有就要停下来想一想能不能把搜索范围缩小。另一个常见误区是混淆“p或q在祖先路径”与“p或q本身”。因为祖先包含自身所以当某个节点本身就是p或q时它自己就可以作为公共祖先的候选。236题代码里那个root p or root q的终止条件就是在处理这种情况绝对不能删掉。最后说一个我自己的实践体会。训练营第十四天的内容多但内部逻辑其实是环环相扣的二叉树的概念支持遍历递归遍历支持迭代遍历统一迭代又反过来深化对递归和迭代的理解层序遍历提供了另一套处理树的方式而最近公共祖先题目正好把所有遍历知识综合起来。我后来再刷二叉树相关题目时只要看到题目要求“从下往上找”“判断两个节点是否在两侧”就会下意识先想后序遍历能不能解决。这个习惯就是从这两道公共祖先题里养出来的非常值得。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
