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, val=0, left=None, right=None): 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 result

size这个值必须在循环一开始就取好，而不是在循环内部动态读取len(queue)。原因很简单：在处理这一层节点的过程中，我们会不断加入下一层的节点，队列长度一直在变，只有提前快照才能保证循环次数是当前层的节点数量。这个细节非常关键，很多层序变体题都依赖这一行。

5.3 层序还能解决哪些变体

层序的框架一旦掌握，可以一口气解决好几道题：自底向上的层序遍历只需要最后把result反转；二叉树右视图只需要在每一层记录最后一个节点；每层最大值用max(level)直接得出；锯齿形层序遍历根据当前层是奇数还是偶数决定是否反转level；N叉树的层序遍历只需要循环访问节点的多个孩子。可以说，你花一小时吃透层序模板，等于同时预习了很多道层序变体的面试题，性价比非常高。

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的终止条件，就是在处理这种情况，绝对不能删掉。

最后说一个我自己的实践体会。训练营第十四天的内容多，但内部逻辑其实是环环相扣的：二叉树的概念支持遍历，递归遍历支持迭代遍历，统一迭代又反过来深化对递归和迭代的理解，层序遍历提供了另一套处理树的方式，而最近公共祖先题目正好把所有遍历知识综合起来。我后来再刷二叉树相关题目时，只要看到题目要求“从下往上找”“判断两个节点是否在两侧”，就会下意识先想后序遍历能不能解决。这个习惯就是从这两道公共祖先题里养出来的，非常值得。