算上今天这次我已经是第三轮把二叉树相关的题目重新刷一遍了还是在写遍历和求深度的时候翻车。说句实在话刚开始跟着网上的刷题路线走我总觉得二叉树就是“递归就完事”的题目类型直到我把《代码随想录》里关于二叉树的那部分完整啃下来才发现以前那种“看懂题解就以为会了”的状态有多假。递归的顺序为什么是那样迭代时栈里到底压的是什么空指针为什么总在你不注意的地方炸出来——这些才是真正拉开差距的地方。这篇文章就是我基于这轮复盘整理出来的二叉树学习笔记覆盖遍历、深度、搜索二叉树、线索二叉树以及“写二叉树程序时为什么总是报运行时错误”这个让新手头大的问题。1. 二叉树为什么值得你专门花时间1.1 二叉树是递归思维的最佳训练场很多算法题你一上来就能用递归但用递归和真正理解递归是两码事。二叉树天然就是递归结构一棵树的左孩子和右孩子又是一棵树所以处理整棵树和处理一个子树用的是同一套逻辑。你把一个函数定义成“处理当前节点再把左右子树交给它自己”这就是递归。代码随想录里反复强调递归三要素终止条件、返回值、单层逻辑。我按这个套路去套二叉树题目思路立刻清晰很多。比如遍历一棵树单层逻辑就是“处理当前节点”下一层交给子树终止条件是“节点为空”因为空树不需要任何处理返回值则根据题目要求决定求深度返回整数收集路径返回列表。说句个人感受二叉树把“问题规模缩小”这件事展现得很直接。你不需要像动态规划那样纠结状态转移也不需要像图论那样考虑环和访问标记所有问题都压在一棵树上左右两条路径逻辑链很短。正因为短你才有机会把递归、栈、队列、指针这些基本功练扎实所以各大算法刷题清单都会把二叉树放在非常靠前的位置。1.2 刷题前后先建立“脑图”式的框架我见过太多人一拿到二叉树题目就打开编辑器写递归结果写到一半开始混乱当前节点要不要先处理左子树返回的值要拿来干嘛什么时候该判空想解决这种问题我强烈建议你在写代码之前先花两分钟做一件事画树。画一棵三层左右的小树标好左右孩子然后从根节点开始把自己的逻辑“手算”一遍。这一遍可能很慢但特别值。比如写前序遍历你在纸上走一遍就会发现输出顺序是根、左、右写最小深度你也会发现单边树的情况很容易被忽略。拿到题目后我还习惯先问自己三个问题这题需要遍历整棵树还是只需要找到某条路径如果是遍历用前中后序哪一种顺序最方便如果当前节点为空时应该返回什么才能不影响上一层逻辑这三个问题想清楚八成以上二叉树题目的代码结构就已经定型了。这也是代码随想录里那个提法的精髓先想清楚“相对固定的模板”和“题目真正变化的点”而不是一上来就闷头写。2. 二叉树的遍历递归和迭代两套都别落下2.1 递归遍历的三种写法与统一记忆法先明确一个基础前提二叉树遍历按处理顺序分成前序、中序、后序三种所谓“前中后”指的是当前节点的访问时机。前序是“处理完当前节点再处理左子树和右子树”中序是“先左子树再当前节点最后右子树”后序则是“先左右子树最后处理当前节点”。我最早是这样记的前中后对应“中间节点在第几个位置被处理”。比如中序遍历中间节点在第二个位置被访问所以顺序是左、中、右。实际写代码时有个固定的模板def traversal(root, res): if root is None: return # 前序res.append(root.val) traversal(root.left, res) # 中序res.append(root.val) traversal(root.right, res) # 后序res.append(root.val)这段模板的含义是到底做什么操作写在左孩子递归前、左孩子递归和右孩子递归之间还是写在右孩子递归后。我把这个位置关系记住之后三种遍历基本不会写错。有个细节需要注意如果你用列表拼接的方式来写比如return [root.val] preorder(root.left) preorder(root.right)在数据量小的时候没问题但每层递归都会产生新的临时列表内存开销偏高。更规范的做法是维护一个res列表用 append 把节点值装进去。这个习惯越早养成越好后面写回溯、路径收集都会用到。2.2 迭代遍历用栈去模拟递归调用栈递归好写但面试官经常要求你换成迭代写法。究其原因递归在底层靠系统栈保存状态我们用显式栈就是在模拟这个过程。前序遍历的迭代很好理解先把根节点压栈然后循环弹出栈顶节点并访问再把右孩子和左孩子压入栈。注意顺序因为栈是后进先出想让左孩子先被访问就得先把右孩子压进去。中序遍历就复杂一些。你没法一上来就访问根节点因为需要先处理完整条左链。做法是从根节点开始只要当前节点不为空就把它压栈并且一直沿左孩子往下走直到左孩子为空弹出栈顶节点并访问然后让当前节点等于它的右孩子继续重复这个过程。这一步藏着很多初学者第一次崩溃的点右孩子为空怎么办那就继续弹栈回到上一层的根节点再访问它。核心就是那句“当前节点为空了就回退到栈顶访问它然后向右走”。还有一个比较取巧的“颜色标记法”适合把三种遍历统一起来。给每个节点打一个状态标记比如 0 表示还没访问过1 表示已经访问过压栈顺序反过来处理就行。以中序为例def inorder(root): stack [(0, root)] res [] while stack: state, node stack.pop() if node is None: continue if state 0: stack.append((0, node.right)) stack.append((1, node)) stack.append((0, node.left)) else: res.append(node.val) return res你只需要记住“前序就按右、左、当前节点压栈后序就按当前节点、右、左压栈”其余逻辑完全一致。这个方法牺牲了一点空间但换来的是思维负担大幅降低我在手撕代码时最喜欢用。2.3 层序遍历队列吃遍天层序遍历也叫广度优先遍历核心数据结构是队列。每一层处理时需要先记录当前队列的长度因为队列后面还会挂入下一层的节点。如果不记录长度你可能会把下一层的节点也当成当前层来处理最后输出的层级就乱了。from collections import deque def level_order(root): if root is None: return [] queue deque([root]) res [] while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res这段代码几乎是层序遍历的标准模板。后面遇到“二叉树最大宽度”“每层最左侧节点”“二叉树的右视图”这类题目都是在套这个模板只是把node.val或level的处理换成题目要求的逻辑。层序遍历返回的第几层是第几个数组这个结构本身也恰好对应树按层展开的形态理解起来非常直观。3. 二叉树的深度坑都在最小深度里3.1 先区分深度和高度的定义严格来说深度是从根节点到某个节点的节点个数高度是从某个节点到最远叶子节点的节点个数。对整棵树来说最大深度通常等于根节点的高度。实际做算法题时很多题目并没有区分这两个词你只需求出从根到最远叶子路径上的节点个数即可。递归终止条件通常是空节点返回 0。这样每个非空节点的深度等于它左右子树的最大深度再加 1。这个加 1 加在哪很关键当节点为空时返回 0处理当前节点时把左右子树的结果取max再1得到的值就是当前节点这棵树的最大深度。因为递归一层层回溯根节点最后拿到的就是整棵树的最大深度。3.2 最小深度的经典误区求最大深度很简单求最小深度却容易出现一个非常隐蔽的坑想当然地写成min(left_depth, right_depth) 1。假设树是一条向左延伸的链根节点的右子树为空。按照这个公式右子树返回 0最小深度会变成 1但题目定义的最小深度是“从根节点到最近叶子节点的最短路径上的节点数”。右子树为空不代表那个空节点是一个叶子节点你根本不能从根走到一个空节点上所以这种情况下正确答案应该由左子树的深度决定。正确的递归逻辑是分三种情况处理如果当前节点为空返回 0如果左孩子为空则往右子树继续求最小深度再加 1如果右孩子为空则往左子树继续求最小深度再加 1如果左右孩子都不为空才取两者较小值再加 1。其实用层序遍历也能解决最小深度问题层序遍历时把层数记录好遇到第一个叶子节点就直接返回当前层数。这个写法的好处是提前终止不用遍历完整棵树在极端瘦长的树上也更稳。3.3 求深度的三种实现方式横向对比递归法写起来最简洁代码量最小但空间复杂度在最坏情况下是 O(n)因为递归栈会随着树的深度增加。链式树会导致递归深度达到节点总数有栈溢出风险。层序迭代法的空间主要花在队列上最坏情况是 O(n)但它天然能处理按层返回这种需求而且不会爆递归栈。另一种迭代法是用栈记录节点和它对应的深度值压栈时把父节点深度加一作为孩子节点的深度最后取最大值这种方法本质上是模拟了递归的遍历顺序代码也不是很难写。从刷题角度来说我建议递归法和层序法都熟练掌握。遇到“求深度”这类普通题目递归法最快遇到“求最小深度”和“按层操作”这类题目层序法会更直观。4. 搜索二叉树与线索二叉树理解起来没那么玄4.1 搜索二叉树的性质决定解法边界搜索二叉树也叫二叉搜索树通常用英文缩写 BST 表示它有一个很强的性质对任意一个节点它左子树上所有节点的值都小于该节点的值右子树上所有节点的值都大于该节点的值而且左右子树本身也各自满足这个条件。这个性质最直接的应用就是查找。在一个平衡的 BST 里查找一个值每次都把搜索范围缩小一半。很多题目一看数据范围就想建红黑树其实就是因为 BST 思想在性能上的极大优势。关于验证一棵树是否是 BST有一个特别典型的误区只看当前节点和它的左孩子、右孩子的大小关系。这只能保证局部正确不能保证左子树里所有节点都比当前值小。比如根节点是 5左孩子是 3但左孩子的右孩子却是 7这棵树局部看起来没问题实际已经违反了 BST 定义。正确做法是给递归函数传递一个有效范围像这样def is_valid_bst(root): def helper(node, lower, upper): if node is None: return True if node.val lower or node.val upper: return False return helper(node.left, lower, node.val) and helper(node.right, node.val, upper) return helper(root, float(-inf), float(inf))左子树更新上界右子树更新下界同时还要保留祖先节点定下的另一侧边界这样整棵树的约束关系才能被完整描述出来。4.2 中序遍历 BST 可以直接得到有序序列BST 还有一个顺手就能用的特性中序遍历结果是一个严格递增的序列。原因是中序顺序本来就是“左子树、当前节点、右子树”再叠加 BST 的节点值关系那自然就是从大到小排好序的。这个特性让很多题变得非常简单。比如“求 BST 中第 K 小的节点”你只需要做一次中序遍历数到第 K 个节点就是答案。比如“把 BST 转换为累加树”你从右往左累加就可以了本质上是中序遍历的反向版本。顺着这个思路你还能理解一个问题很多题目要求的答案是一棵树的节点顺序而不是值本身这个时候遍历顺序就是算法的骨架剩下的只是具体业务逻辑。我在刷 BST 系列题目时一旦看到“有序”“第 K 大”“累加”这些关键词几乎都会优先考虑中序遍历这个切入点。4.3 线索二叉树的本质是“利用空指针”线索二叉树这个概念看起来有点古老但理解它非常有价值。普通二叉树上存在大量空指针对于一个有 n 个节点的二叉树空指针数量是 n1。线索二叉树的思想就是把这些空指针利用起来让节点原本空着的左指针指向它的中序前驱原本空着的右指针指向它的中序后继。为了区分指针到底是孩子还是线索每个节点还需要增加两个标志位比如left_tag和right_tag。当标志为“线索”时左右指针指向的是遍历序列中的前驱后继当标志为“孩子”时左右指针才指向真实子树。你甚至可以手工构造一棵线索树然后顺着线索快速找到某个节点在中序遍历中的后继不需要再来一次递归。这个思路之所以重要是因为它引出了 Morris 遍历。Morris 遍历利用叶子节点的空指针把中序遍历的空间复杂度优化到了 O(1)在不需要输出整棵树的前提下非常优雅。虽然面试很少让你完整实现 Morris 遍历但你能讲清楚它的原理说明你真的理解了树的遍历和指针利用而不是只会套模板。5. 写二叉树程序时为什么总是报运行时错误——排查实录5.1 第一大元凶空指针访问二叉树的运行时错误大部分都是空指针问题。Python 里常见的是AttributeError: NoneType object has no attribute valC 里则是直接段错误。归根结底你访问了空节点上的字段或方法。最容易出错的场景是判断当前节点是否叶子节点时写成if root.left.val is None。此时如果root.left本身就是空节点那root.left.val就直接炸了。正确做法应该先判空再访问写成if root.left is not None and root.left.val is not None。递归函数的开头加一句判空几乎成了二叉树题目的安全口诀。你可以判断root is None就直接返回一个空列表、0、True 或者 None具体返回什么看题目要求。只要递归入口都判空大部分空指针问题都能被掐死在源头。5.2 第二大元凶递归栈溢出递归写起来舒服但系统给递归调用栈分配的空间是有限的。当二叉树的形状极度不平衡比如退化成一条链表节点数有几万甚至几十万时递归深度就会和节点数相同然后触发递归深度限制。Python 会报RecursionError: maximum recursion depth exceededC 则直接栈溢出。做算法题时这通常不是树本身的问题而是你选择的方法不合适。如果题目明确说树的高度可能很大或者你可以预见到最坏情况是链式树那就考虑用迭代法。层序遍历求深度、用栈模拟中序遍历这些写法都能把递归依赖去掉。还有一个容易忽略的点递归函数里如果写了return recursion(left) recursion(right)两个递归调用求值顺序虽然不一定是并行的但在极端情况下调用栈会累积得比较深。我对这种合并型递归的警惕心会更高遇到深树时会特别留意。5.3 第三大元凶边界条件写错还有很大一部分“运行时错误”实际上是逻辑边界写错导致的。最常见的两个最小深度没处理单边树导致结果错误而不是崩溃递归返回值类型不一致导致后续代码拿到 None 去加减乘除。我见过一个很有趣的报错求最小深度的代码在左右孩子都为空时返回 1在左孩子为空时返回min_depth(root.right) 1但漏了右孩子也为空的情况最终在某个单边树上返回了 0。这类问题不报错但结果就是错的比崩溃更难排查。遇到边界问题最好的办法是构造几个特殊用例跑一遍空树、只有一个根节点、只有左子树、基本完全二叉树。这四类用例跑通大部分边界问题都会被暴露出来。5.4 通用排查套路最小复现路径每次遇到报错我都会走一套固定流程。先看报错信息定位到具体哪一行代码出了异常然后看访问的对象是不是可能为空。接着把完整的测试树缩小成能触发问题的最小树。一棵大数万节点的树我会逐步删掉不相关的节点直到只保留能够复现问题的那个路径再模拟一次执行过程问题往往很快就浮出水面。也可以给递归函数加两行打印函数进入时打印当前节点的值函数返回时打印返回值。这样你能直观看到递归的顺序和数据流动。篇幅多但不会误导尤其适合那种“为什么结果多了一个节点”的逻辑问题。我练了这么多轮最大的体悟是二叉树题目在代码随想录里的体系非常成系统先遍历后深度再 BST 和线索树由浅入深。写代码时多问自己“空节点返回什么”“当前节点的操作放在哪个位置”“左右子树的返回值怎么合并”运行时报错会大幅减少。如果你现在还在被这些细节折磨别着急这都是必经的过程。把这篇笔记里的常见坑都过一遍你再回去写二叉树的题目手感会完全不一样。