前阵子完整过了一遍代码随想录的二叉树专题刷完最大的感受是二叉树这块内容根本不用靠题海去堆真正值钱的是一套能反复套用的遍历框架和递归设计思路。很多人在树这里卡住不是因为题目难是因为把递归、回溯、前中后序这些概念当成了零散知识点没有串成一条线。这篇就把我刷完这个专题后沉淀下来的东西全部倒给你从遍历的底层逻辑、递归的三要素到深度、路径、构造、二叉搜索树这些高频题型的固定打法以及我踩过的一些坑一次讲透。这篇适合三类人看刚开始刷二叉树、想找一条不劝退学习路线的新手刷了不少树题但对递归返回值、迭代顺序、回溯时机还发懵的进阶选手以及准备面试前想把二叉树常见题型快速过一遍的开发者。对我来说这个专题最厉害的地方是把树形问题全部收敛到“遍历顺序”和“递归函数的三个设计要素”上只要把这两个东西吃透后面一大半题都能自己推出来。下面我不按目录顺序讲而是按我自己刷完之后复盘出来的认识顺序拆先搞清楚树为什么难再搞定遍历然后学会设计递归最后带着框架去啃各类高频题型。文末会附一份我自己整理的刷题顺序和错误清单可以直接抄作业。1. 二叉树专题为什么值得单独拎出来刷1.1 树形结构是递归思维的天然试验场数组、链表这些线性结构你按顺序遍历就能遍历完思维负担比较小。树不一样每个节点分出两个分支天然的“分支结构”逼着你考虑“同一个处理逻辑如何在子结构上重复执行”。这个重复执行正好就是递归能干的活。更关键的是二叉树本身的定义就是递归的一棵二叉树由根节点、左子树、右子树组成而左子树、右子树又分别是一棵二叉树。所以“处理一棵树”这个任务天然可以拆成“处理根节点 处理左子树 处理右子树”左右子树又是同样的问题只是规模更小。这种“原问题包含同构子问题”的特征在数组和链表上并不明显在树上却处处体现。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right这就是二叉树节点的标准定义。很多解法看起来简洁到不可思议底层就是因为它把“递归就是树树就是递归”这件事用到了极致。面试喜欢考树考的不只是你是否背下了某个模板更多是考察你有没有理解递归的执行过程、边界条件、返回值和空间复杂度。而这些能力恰恰是在数组和链表题目里很难练出来的。1.2 这个专题的题型地图先知道终点再看路刷题最怕闷头刷。这个专题我建议先建立一张题型地图心里有全局再逐个击破。按代码随想录二叉树专题的编排思路常见题型大致可以分成六类题型分类典型问题核心手段遍历类前序、中序、后序、层序遍历递归 / 迭代栈 / 队列属性类最大深度、最小深度、节点数、平衡判断递归返回值、后序高度路径类路径总和、所有路径、最大路径和回溯、前序路径记录构造类前序中序还原树、有序数组转BST递归切分区间搜索树类验证BST、搜索、插入、删除、公共祖先中序有序、二分方向形态类翻转、合并、对称、子树判断递归同步比较结构你可能会发现所有类的解法到最后都回到两个底层能力一是递归函数的“返回值”和“单层逻辑”设计二是遍历顺序的选择。所以第二章先死磕遍历这不是绕路而是最短路。1.3 语言选型与基础实现用最顺手的工具先跑起来刷这个专题用什么语言我的建议是你日常用什么就先用什么但一定要把树的节点定义和基本前序遍历背到肌肉记忆。用 Python 刷树的体验确实舒服代码简洁、不容易被语言细节干扰思路适合快速验证递归想法用 C 或 Java 则更贴近很多公司面试时的手写代码习惯对空指针、引用传递这些细节的敏感度也更高。有一点我要单独提醒不管用什么语言都建议先明确“空树”的表示。在线判题平台上空树就是根节点为空指针或 None。很多递归写错都是因为终止条件没有处理“传入空节点”的情况导致访问了空指针的左右孩子直接崩掉。后面第三节我会专门讲终止条件的设计这里是第一个容易埋雷的地方。2. 遍历三件套递归、迭代与层序的底层逻辑2.1 递归遍历三行代码背后的执行顺序先看递归遍历。前序、中序、后序的代码长得几乎一样区别只在将“处理根节点”这一行放在哪个位置def preorder(root): # 前序根 - 左 - 右 if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): # 中序左 - 根 - 右 if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): # 后序左 - 右 - 根 if not root: return [] return postorder(root.left) postorder(root.right) [root.val]很多人背下了这三段代码却没有理解“什么时候去递归左子树什么时候去递归右子树什么时候处理根节点”之间的先后关系。递归遍历的执行顺序本质上是深度优先搜索DFS加上一个“记录时机”前序是进入节点时记录中序是左子树处理完后记录后序是左右子树都处理完后记录。我让 A同学 在纸上画一棵三层满二叉树手动模拟一遍前序遍历的递归调用栈他的反应是“原来递归不是从根节点一路往左到底吗怎么还会跳到右边去”。这就是关键每个节点都会先执行完自己的左子树再执行自己的右子树。前序遍历看起来是“一路向左”但每当一个节点的左子树走完就会回溯到该节点然后进入右子树。这个“回溯”过程如果没在脑子里跑一遍后面看迭代法和回溯题都会晕。2.2 迭代遍历用栈模拟系统栈时最容易踩的坑递归的本质是借用系统栈保存现场。迭代遍历就是不用系统栈自己拿一个显式栈来模拟。前序遍历的迭代版最容易理解def preorder(root): res [] 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这里有一个新手必踩的坑出栈顺序是先左后右所以入栈时反而要先压右孩子、再压左孩子。你如果顺手先 push left再 push right那实际遍历顺序就变成了“根 - 右 - 左”前序遍历就错了。这种顺序上的反直觉正是迭代遍历比递归遍历更容易写错的地方。中序迭代和前序不太一样它需要“先把整条左链压入栈再逐个弹出的过程中访问节点并转向右子树”def inorder(root): res [] stack [] cur root 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 or stack导致遍历完左链后循环直接退出后续节点全部丢失。这个错误很隐蔽因为对一棵没有右子树的树来说结果碰巧是对的。2.3 层序遍历队列的宽度优先思想为什么是万能钥匙层序遍历和前面三种完全不同它是广度优先搜索BFS依靠队列而不是栈。一次入队一层的全部节点出队时再把它们的子节点入队from collections import deque def level_order(root): if not root: return [] res [] q deque([root]) 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这段代码里最能体现“一键多节点”的是for _ in range(len(q))。这里有一个细节我必须强调range(len(q))在进入循环的那一刻就已经固定了即使循环里不断把子节点加入队列这一轮也只会处理最开始那一层的节点数量。如果你写成while q:又在循环里 append 子节点那么所有节点会被混在一层层次就没了。这个特性是层序遍历能按层输出的根基也是“求每层最大值”“层内锯齿遍历”“右视图”这类变形题的共同基础。2.4 统一迭代法一个 None 标记解决处理与访问的矛盾我发现很多人刷完递归和迭代后会陷入一个麻烦前序迭代、中序迭代、后序迭代三种写法结构都不一样背了又忘。代码随想录的二叉树专题里我印象很深的是给了统一风格的迭代写法用栈遍历时在“访问”和“处理”之间插入一个空节点标记。什么叫“访问”和“处理”访问是指把节点压入栈等待后续处理处理是指真正把节点的值加入结果数组。递归里这两件事是隐式靠调用时机区分的迭代里你得自己控制。统一迭代法的思路是把每个需要处理的节点再次入栈并在它上方放一个 None 标记。弹出 None 时说明下一个栈顶元素已经左右子树处理完毕可以放心输出。以中序为例def inorder(root): res [] stack [root] while stack: node stack.pop() if node: if node.right: stack.append(node.right) stack.append(node) stack.append(None) if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res后序只需要调整入栈顺序def postorder(root): res [] stack [root] while stack: node stack.pop() if node: stack.append(node) stack.append(None) if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res这套统一写法的价值不只是“代码结构一致”更重要的是帮你建立“访问顺序由压栈顺序决定”的意识。后序要求“左 - 右 - 根”压栈时就把根先压进去、加 None 标记然后压右孩子、压左孩子。弹出时因为有 None 挡着根节点一定在最晚被处理。理解了这套逻辑你以后看任何“用栈实现树的遍历”的代码都不会再觉得是魔法。3. 递归函数的三个设计要素终止条件、返回值与单层逻辑3.1 什么时候该返回值什么时候该用全局变量刷树题时很多人不知道递归函数到底该返回什么。我的经验是先把问题问清楚上一级节点需要从我这里拿到什么信息求深度、求高度、判断平衡上一级需要的是“子树的高度”返回 int判断“是否存在某条路径”上一级需要的是布尔真假返回 bool根据前序中序构造树上一级需要的是“整棵子树”返回 TreeNode收集所有路径上一级不需要汇总具体信息只需要往下传一个路径列表返回 None 或自由递归即可。一个加分的理解是需要“自底向上汇总信息”的基本都要用返回值只是“自顶向下记录过程”的通常用参数传递 全局/外部容器收集。这个判断能帮你避免大量“不知道 return 什么”的卡壳。比如翻转二叉树def invert_tree(root): if not root: return None root.left, root.right invert_tree(root.right), invert_tree(root.left) return root这里虽然翻转动作发生在每个节点但必须返回新的子树根因为要把结果接回父节点。如果你写成root.left invert_tree(root.left)再root.right invert_tree(root.right)然后不返回根顶层调用拿到的是 None树就丢了。3.2 终止条件怎么写才不漏递归里终止条件写错比返回值选错更容易导致灾难。最常见的问题是“空节点终止”和“叶子节点终止”混用。只举一个例子求最小深度。很多人的第一版是def min_depth(root): if not root: return 0 return 1 min(min_depth(root.left), min_depth(root.right))这版代码在“树只有左子树、没有右子树”时结果是错的。因为空右子树返回 0min(左子树高度, 0)直接取到 0整个结果被空叶子带偏。正确的思路是最小深度是从根到最近叶子节点的距离终止条件必须以“叶子节点”为边界def min_depth(root): if not root: return 0 if not root.left: return min_depth(root.right) 1 if not root.right: return min_depth(root.left) 1 return min(min_depth(root.left), min_depth(root.right)) 1这个例子非常典型地说明“空节点返回 0”在最大深度里成立在最小深度里却不成立因为最大深度的天然下界是 0最小深度的天然下界是无穷大。你只有理解了“这个终止条件到底在表达什么含义”才能在不同题目里灵活调整而不是死记模板。3.3 单层逻辑的顺序前序、中序、后序分别解决什么问题单层逻辑是指“当前节点要做的动作以及先做哪个、后做哪个”。这个顺序对应遍历顺序前序先处理根节点再递归中序先递归左子树再处理根节点后序最后处理根节点。不同顺序对应不同场景前序适合“自顶向下做决定”。比如翻转二叉树你要把当前节点的左右孩子互换再往下递归中序适合“利用二叉搜索树的有序性”。BST 中序遍历结果是升序序列验证 BST、求第 k 小节点都靠这个顺序后序适合“自底向上汇总”。判断平衡、求高度、最大路径和都是先知道左右子树的情况才能决定当前节点的状态。我经常用一个生活化类比前序像领导先拍板再往下布置任务中序像按文件柜顺序逐本检查后序像先收集完所有现场证据再做结论。选错顺序题不是不能做而是思路会变得很别扭。这个专题里几乎所有“为什么这样遍历”的答案都能从这三维度里找到解释。4. 高频题型的解题框架从一棵树到多条路径4.1 求深度与求高度一个词之差遍历方向就反了深度是从根节点往下数的层数高度是从叶子节点往上数的层数。最大深度等于根节点的高度所以既可以用前序向下传深度也可以用后序向上返回高度。我推荐后序def max_depth(root): if not root: return 0 left max_depth(root.left) right max_depth(root.right) return max(left, right) 1这个代码非常短但值得拆解递归进入左子树拿到左子树高度进入右子树拿到右子树高度取较大者加 1 就是当前节点高度。遇到空返回 0就是“空树高度为 0”的基准。把这段代码吃透等于同时学会了“后序汇总”这个最常用的树形递归模式。前面说过的深度和高度概念区分在这里就是“前序记录”与“后序汇总”的区别千万别搞反。4.2 判断平衡二叉树后序求高度时提前剪枝判断一棵树是否平衡常规想法是对每个节点都求左右子树高度再检查差值。但如果你对每个节点单独调用一次求高度函数时间复杂度会退化到 O(n^2)因为每棵子树被反复递归计算。更优的做法是后序递归时顺便返回高度一旦发现左右子树高度差大于 1就直接返回一个特殊标记表示“这里已经不平衡了”def is_balanced(root): def height(node): if not node: return 0 left height(node.left) right height(node.right) if left -1 or right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return height(root) ! -1这里的 -1 就是“剪枝信号”只要有一棵子树不平衡上层递归会立刻沿着 -1 一路返回不再继续检查其它节点。这个模式在树形题里特别常用本质上是把“合法性校验”内嵌到“信息收集”的过程中比先算完全部信息再整体校验要省很多不必要的计算。4.3 路径问题回溯姿势在这个专题里怎么摆路径类题目是二叉树从“单节点处理”走向“一路记录”的转折点。典型的是“路径总和”和“收集所有路径”它们的核心是前序遍历 回溯。看路径总和这个经典题def has_path_sum(root, target_sum): if not root: return False target_sum - root.val if not root.left and not root.right: return target_sum 0 return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)注意这里target_sum是按值传递的每次递归都有自己的副本所以这个版本其实不需要显式回溯递归返回后自动恢复原值。但如果要收集路径本身就必须用共享的列表并在递归返回前把当前节点弹出def binary_tree_paths(root): res [] def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append(-.join(path)) else: dfs(node.left, path) dfs(node.right, path) path.pop() dfs(root, []) return res这里path.append与path.pop成对出现就是回溯的标准姿势。很多人在树里忘了 pop导致左子树的路径残留到右子树的结果里输出一堆奇怪字符串。我的经验是只要看到递归函数传入的是一个容器对象list、path、数组就要马上检查它是否在递归返回后被还原。这个习惯能帮你避开树路径题里至少一半的 bug。4.4 树的构造前序中序还原二叉树的关键推导构造类题目在专题里属于“综合应用题”因为它同时考察数组切分和递归构造。给出前序和中序序列还原二叉树def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left build_tree(preorder[1:idx1], inorder[:idx]) root.right build_tree(preorder[idx1:], inorder[idx1:]) return root推导逻辑是前序第一个元素一定是根在中序里找到根的位置 idx那么中序左边[0, idx)就是左子树的所有节点右边(idx, end]就是右子树的所有节点。因为左右子树节点数量定了前序里除去第一个根节点后前idx个属于左子树剩下的属于右子树。这里我强烈建议全程坚持“左闭右开”区间preorder[1:idx1]对应左子树inorder[:idx]也对应左子树两个区间的边界逻辑完全一致不容易乱。等递归到最后区间为空自然返回 None正好是构造递归的终止条件。我知道有个代码细节很不起眼却影响巨大inorder.index(root_val)每次都要在数组中线性搜索整体复杂度是 O(n^2)。如果只是做对题目这样够了但如果序列很长建议先用哈希表记录中序元素的下标再在递归里通过区间索引取值。这是从“功能正确”走向“性能正确”的典型优化点。5. 二叉搜索树不是普通的树有序性带来的特殊套路5.1 中序序列有序验证BST为什么不能只比较左右孩子二叉搜索树BST的核心性质是左子树所有节点小于根右子树所有节点大于根。很多人第一反应是“我只要判断node.left.val node.val node.right.val就行了”这个做法是错的。因为 BST 要求“所有”左子树节点都比根小而不只是直接的左孩子。举个反例一棵树根为 10右孩子为 12右孩子的左孩子为 9这棵树局部满足比较但 9 出现在根的右子树里整棵树不是 BST。正确的验证方法有两种一是维护上下界递归传递二是利用“中序序列递增”这条性质。我用上下界法def is_valid_bst(root): def dfs(node, low, high): if not node: return True if not (low node.val high): return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root, float(-inf), float(inf))理解这段代码的关键是每往左走上界被收紧为当前根值每往右走下界被收紧为当前根值。全部节点都必须落在相对根的区间内。另一种思路是把中序遍历结果收集出来检查是否严格升序同样可行但要额外开一个数组。中序法我在实际做题时更常用因为代码更短而且顺带预演了“BST 中序有序”这条黄金结论。5.2 有序数组转平衡树取中点与均衡分割将有序数组转换成平衡二叉搜索树是“BST 构造”的结合题。平衡要求左右子树高度差不超过 1想到的最直接办法就是递归取中点def sorted_array_to_bst(nums): if not nums: return None mid len(nums) // 2 root TreeNode(nums[mid]) root.left sorted_array_to_bst(nums[:mid]) root.right sorted_array_to_bst(nums[mid1:]) return root为什么取中点就能保证平衡因为每次取中点左右两部分的元素数量差最多只有 1递归下去每层左右子树的规模都几乎是均衡的整棵树的高度就稳定在 log n。这个构造过程是对“二分思想”最好的复习数组的中间元素是中序遍历顺序中的根左边一段继续构造左子树右边一段继续构造右子树。5.3 最近公共祖先与区间查询BST的高效搜索方向BST 的有序性让“从根向下搜索”有了明确方向。求两个节点的最近公共祖先如果是普通二叉树需要后序遍历从底部汇聚结果在 BST 里却能利用节点值比较直接二分def lowest_common_ancestor_bst(root, p, q): while root: if root.val p.val and root.val q.val: root root.right elif root.val p.val and root.val q.val: root root.left else: return root这段代码的逻辑是如果 p 和 q 都在右子树当前根就是小了往右走都在左子树就往左走如果 p、q 分别位于两侧或者当前根等于其中一个那当前根就是最近公共祖先。这个题用普通二叉树也能做但 BST 版本把“根据值搜索方向”的优势发挥到了极致也提醒我一个重要观点题目给了 BST 这个条件一定是让你利用有序性的别傻乎乎地按照通用树的笨办法硬解。6. 刷完这个专题后我自己沉淀的复盘笔记6.1 刷题顺序建议一套不太会劝退新手的路线我自己的建议顺序是先刷遍历三件套递归前中后序 - 迭代前中后序 - 层序再刷属性类最大深度、最小深度、节点数、平衡然后刷路径类所有路径、路径总和、最大路径和接着刷构造类前序中序还原、中序后序还原、有序数组转 BST最后刷 BST 专属题验证、搜索、插入、删除、公共祖先。这个顺序背后有一条明确的依赖链不把遍历吃透递归设计和层序思维就是空中楼阁不把递归三要素掌握路径和构造题会被各种终止条件和回溯时机折磨不把 BST 性质理清验证搜索树的题就容易写出“只比左右孩子”的错误判断。6.2 容易写错的细节清单我把自己线上调试时常见的错误整理成了一个小表刷题前扫一眼能省很多时间细节典型错误正确做法层序的层固定while q时动态 append分层失效先取len(q)再循环该层节点迭代前序入栈顺序先 left 后 right输出变根右左先右后左入栈最小深度终止空节点返回 0 直接 min单子树时按非空分支继续递归路径收集回溯递归后忘记 popappend 与 pop 成对出现BST 只比邻居root.left.val root.val就通过用上下界或中序递增验证构造树区间切片边界忽左忽右全程左闭右开保持统一这些错误几乎是每个刷二叉树的人都会遇到的。它们不是知识量不够而是对“递归的隐式状态”和“区间边界的一致性”不够敏感。刷题时出一次错停下来分析一次根因比闷头连做二十道题更有用。6.3 从二叉树到后续专题的思维迁移二叉树专题最让我受益的并不是学会了多少道题而是把递归、回溯、DFS、分治这些抽象概念全都在一棵棵具体的树上落地了。之后刷回溯专题你会想起路径类题目里 append 和 pop 的成对出现刷图论时你会想起层序遍历的队列其实就是 BFS 的原理雏形刷动态规划时树形 DP 里“后序汇总子树信息”的模式跟判断平衡树的返回值设计几乎如出一辙。所以如果有人问我二叉树专题到底该怎么刷我的回答始终是不要急着记题号先把遍历顺序、递归三要素、BST 性质这三根柱子立起来剩下的题目都是柱子上挂的不同装饰。我自己当时把专题里最基础的几道题用三种遍历顺序各写了一遍再去做构造和 BST 题明显感觉不是背题而是推导。这种“能自己推出来”的感觉才是刷完这个专题最值得留下的东西。
