二叉树详解：递归遍历、搜索二叉树与运行时错误排查

1. 先理解二叉树：别被名字吓住，它只是“每个节点最多俩孩子”的树

很多朋友学到数据结构，第一个卡住的坎往往不是链表，而是二叉树。链表好歹还能靠“穿珠子”的直觉理解，二叉树一说“递归”“左右子树”，脑子就嗡嗡的。我当年第一次用指针写二叉树，也是在深夜对着控制台的“Segmentation fault”怀疑人生——后来想通了，二叉树的本质其实非常简单：每一个节点最多有两个分支，分别叫左孩子和右孩子，剩下的所有概念都建立在这句话之上。

先不要急着背遍历的代码，先把“为什么是二叉树”想明白。现实中很多结构天然就是二叉的：人的家族谱是树，但一个人可能有多个孩子，那是普通树；而二叉树约束了“最多两孩子”，这个看似武断的限制，反而让存储、查找、遍历都有了极其稳定的规律。计算机领域有一句经验之谈：能转换成二叉树处理的结构，尽量转换成二叉树，因为左右两个子树的递归处理模式太成熟了，几乎形成了一套工业级的标准打法。

另一个为什么要学二叉树的原因是：离开大学之后你会发现，几乎所有高效容器的底层结构都离不开树，而树最基本形态就是二叉树。数据库索引、编译器表达式解析、文件目录的优化存储，底层都藏着二叉树或者由它拓展而来的变体。你现在花时间把二叉树学透，后面看HashMap的红黑树、看AVL旋转、看堆排序，都会觉得“哦，原来都是老朋友”。

还有一点想提醒初学者：学二叉树别死记代码，要死记“想法”。二叉树的所有操作几乎都能归结为一句话——“对当前节点做什么，对左子树做什么，对右子树做什么”，这就是递归的三段式。你把这句话刻进脑子里，比背五十行代码都有用。

1.1 二叉树的递归本质：每个节点都在重复同一件事

我见过太多人学二叉树，上来就画了一棵三层的大树，然后盯着根节点发呆，觉得这玩意儿太复杂。其实正确的学法应该是盯着一个节点看：它有一个值，有一个左指针，有一个右指针。放到递归框架里，我们要处理的“当前节点”永远只是这一个小方格，剩下的交给递归去处理。

我们用以下这个最经典的“访问全部节点”结构来说：

void traverse(TreeNode* node) { if (node == NULL) return; // 递归出口：走到了叶子下面的空指针 // 这里做你想做的操作，比如打印值 printf("%d ", node->val); traverse(node->left); // 把左子树整体当作一个新“根”，重复同一套逻辑 traverse(node->right); // 把右子树整体当作一个新“根”，重复同一套逻辑 }

这段代码之所以能遍历整棵树，根本原因在于：每一棵子树在结构上和整棵树是“同构的”。左子树本身也是一棵二叉树，它有根、有左右孩子，所以对根节点执行的逻辑，对左子树的根节点同样成立。这就是递归能够成立的数学基础——自相似性。你可以把递归理解成俄罗斯套娃：每一层打开都是一个相似的小一号的娃娃，直到打开到最小的那个（空指针），就停下来了。

理解这一点后，你再看“二叉树的深度”“求节点个数”“判断是否对称”，你会发现所有题目的解法全都长一个样：处理当前节点 + 递归调用左右子树 + 合并返回结果。这不是套路，而是二叉树天然的结构决定了你只能这么思考。

1.2 二叉树的存储方式：链式存储与顺序存储各有各的命

写二叉树之前，得先决定数据怎么放。链式存储是最常见的，每个节点里放数据、左指针、右指针，动态分配内存，用起来灵活，也是各种算法题默认的形态。它的优点是树长成什么样，内存就怎么组织，不会浪费空间；缺点是每个节点要额外存两个指针，有开销，而且找父节点不方便（需要额外加parent指针或者遍历查找）。

顺序存储则用数组存二叉树，根节点放下标1（有些教材放0，但放1做索引更方便），然后某个节点下标为i，其左孩子在2*i，右孩子在2*i+1。这种方式的槽点很明显：如果是一棵“斜树”，也就是每层都只有一个孩子，比如一直往左长，那数组得开得非常大，中间会有大量空位。但如果是完全二叉树或满二叉树，顺序存储就非常香，因为下标能直接算出父子关系，连指针都不需要，内存连续，缓存命中率还高。

我个人的建议是：初学阶段把链式存储吃透，因为面试笔试几乎都是链式；等理解了二叉树的本质之后，再去感受顺序存储，你会发现用数组写堆排序的时候特别顺手，其实堆就是一棵顺序存储的完全二叉树。数据结构这东西，存储方式服务于操作需求，没有绝对的好坏，只有适不适合。

1.3 二叉树的关键形态：满二叉树、完全二叉树、斜树的实用意义

为什么要把形态单拎出来说？因为后面你会遇到很多基于形态的题目和优化。满二叉树很好理解：除了最后一层无任何子节点，其他每一层节点都是满的。完全二叉树则是“满二叉树的从右往左减掉若干叶子”，它的特点是最后一层的节点靠左排列。

完全二叉树的工程价值非常大。前面说的顺序存储，只有对完全二叉树才是空间无浪费的；堆这种数据结构，就是建立在完全二叉树上。还有，判断一棵树是不是完全二叉树，是很多考察层序遍历的题目的高频变体，思路是：层序遍历的过程中，一旦出现空节点，后面的节点就必须全部为空，否则就不是完全二叉树。这句话建议你记住，面试经常考。

斜树则是最不理想的形态，说难听点，它退化成了链表。比如所有节点都只有右孩子，那你用二叉树搜索和用链表线性搜索，复杂度没差别。学到这里你就明白，二叉树的效率优势建立在“平衡”的基础上，这也是为什么后面要引入平衡二叉树、AVL、红黑树这些旋转操作，本质上都是在和“斜树退化”作斗争。

2. 遍历二叉树：三种深度优先遍历的实战手感

遍历是二叉树操作里的基础，也是高频热词“二叉树的遍历”的核心。你先记住一个结论：所谓先序、中序、后序，区别只有“访问根节点的时机”，访问左子树和右子树的相对顺序永远固定是“先左后右”。市面上有不少口诀，其实不用背，你在纸上画一棵三层的小树，用“根左右的顺序”逐个写一遍，几遍就熟了。

在代码层面，三种遍历的递归框架完全一致，区别就一行：

// 先序：根左右 printf("%d ", node->val); preorder(node->left); preorder(node->right); // 中序：左根右 inorder(node->left); printf("%d ", node->val); inorder(node->right); // 后序：左右根 postorder(node->left); postorder(node->right); printf("%d ", node->val);

很多教材把这段代码直接丢给学生，导致不少人对遍历的理解停留在了“背代码”层面。我见过的最实用的理解方式，是把调用栈模拟一遍：程序每一次递归调用前，会把当前函数的状态（局部变量、执行位置）压入系统栈，递归返回时再从栈里弹出来继续执行。所以先、中、后序的执行顺序，本质上是三趟“经过”节点的路径，只不过打印时机不一样。理解了这个，后面写非递归遍历就顺理成章了。

2.1 递归遍历的两个常见坑：出口写错和顺序搞混

递归遍历的坑，新手一踩一个准。第一个坑是出口判断写错。很多人会用node->left == NULL && node->right == NULL作为出口，也就是判断到叶子就停。这做法说不上错，但在某些操作（比如加一个节点）下面，会漏处理一种情况。更干净的做法是直接判断node == NULL，在空指针处返回，让叶子节点也走一次统一的处理逻辑。这样写，代码简洁且不容易漏边界。

第二个坑是把中序的“访问节点”和“递归调用”的顺序搞混。有朋友跑出来发现“怎么输出结果是从中间开始的”，我一看，他把inorder(node->left)写在打印后面了，这不就变成先序了吗？这三个遍历的差异就这一行代码的顺序，写的时候一定要分清楚：中序是先彻底走完左子树，回到根打印，再去右子树。你把递归想成“任务委托”——先委托左子树干活，它全干完了，你自己再打印，然后再委托右子树。这个心理学模型很管用。

2.2 非递归遍历：用显式栈模拟系统调用

递归虽然好写，但有两个问题：一是树特别深时，系统栈可能会爆掉；二是有些场合显式用栈更容易控制流程，比如要“随时暂停遍历”。所以面试和比赛中，非递归遍历是加分项，一定要会。

先序非递归的逻辑最简单：根先入栈，弹出即打印，然后把右孩子先压栈（因为栈是后进先出，右孩子后弹出，左孩子先弹出），再把左孩子压栈。循环到栈空为止。代码大概是：

void preorderIterative(TreeNode* root) { if (root == NULL) return; Stack* stack = stackCreate(); push(stack, root); while (!stackEmpty(stack)) { TreeNode* node = pop(stack); printf("%d ", node->val); if (node->right) push(stack, node->right); if (node->left) push(stack, node->left); } stackFree(stack); }

中序非递归稍微绕一点，核心思想是“一直往左走，走不动了才打印并转向右子树”。用一句话概括：某个节点要出栈时，说明它的左子树已经处理完了。写代码时需要两层循环，外层判断栈非空或当前节点非空，内层不断把当前节点的左孩子压栈。到了最左边之后，弹出节点打印，然后cur = cur->right继续循环。这个过程如果你自己拿笔记模拟一遍，会比看十遍代码都管用。

后序非递归最麻烦，因为根要等左右子树都处理完才能打印，等于打了“两次经过才访问”的标记。最简单的实现思路是用两个栈：第一个栈做“根右左”的遍历，弹出的结果放到第二个栈里，最后再依次弹出第二个栈，就变成了“左右根”。这也是应试技巧：与其硬记复杂的单栈标记法，不如双栈直接换顺序，稳得多。

2.3 层序遍历：用队列实现“逐层扫荡”

层序遍历的思路跟深度优先完全不一样，它不是沿着一条路走到黑，而是按层从上到下、从左到右逐个访问。实现工具是队列，而不是栈。核心逻辑：根节点先入队；每次从队头出一个节点，打印；然后把这个节点的左孩子、右孩子依次入队。因为队列是先进先出，所以天然保证了“上一层先访问”的顺序，孩子们的顺序也能保持从左到右。

void levelOrder(TreeNode* root) { if (root == NULL) return; Queue* q = queueCreate(); enqueue(q, root); while (!queueEmpty(q)) { TreeNode* node = dequeue(q); printf("%d ", node->val); if (node->left) enqueue(q, node->left); if (node->right) enqueue(q, node->right); } queueFree(q); }

层序遍历的重要变体是“按层分组输出”，比如返回一个二维数组，每行是一层节点。做法是在循环里，先取当前队列的长度levelSize，然后只弹出levelSize个节点，这样就能把同一层的节点单独处理成一个层次列表。这个技巧在“求每层最大值”“层序锯齿形遍历”“判断完全二叉树”里都会用到，属于高频复用知识点。

3. 二叉树的深度与形态计算：从递归到递推的实践

热词里“二叉树的深度”排得挺靠前，这也确实是基础操作里最经典的入门题。二叉树的深度定义为从根节点到最远叶子节点的最长路径上节点的数量。空树的深度是0，只有根节点的树深度是1，这是约定俗成的口径。

递归写法就一行核心逻辑：depth = max(depth(left), depth(right)) + 1。因为根节点的深度，等于左右子树中较深的那个，再加上根节点自己。这个思路非常符合二叉树的自相似性：左子树和右子树分别求出深度，谁高算谁。代码我就不重复贴了，简单到一眼就能看懂，但我想强调一个容易忽略的边界：递归调用子树前，不需要判断子树是否为空，因为空树会通过递归出口返回0，这是递归写法最优雅的地方。你越是想在入口处做一堆判空，代码越容易写乱。

3.1 用“求深度”这道题吃透递归的返回值设计

很多初学者会把求深度的递归和遍历的递归混为一谈。遍历强调的是“过程”，你打印了哪些节点；而求深度强调的是“结果”，你要向上层返回一个数值。这里的关键设计问题就是：递归函数的返回值到底含义是什么？在求深度里，返回值是“以当前节点为根的子树深度”。那么递归调用的逻辑就是：先问左子树“你有多深”，再问右子树“你有多深”，取大的加1，回报给父节点。

这是一种“由下往上汇总”的递归模式，和遍历那种“从上往下派出任务”正好相反。我建议你把这两种模式当成两个模板记录下来：遍历模板关注“对当前节点做什么”，汇总模板关注“向上返回什么”。二叉树里百分之六七十的题目，要么是这两种模板之一，要么是它们组合。

实操中还有一个细节：求深度的递归，如果树的深度非常大（比如上万层），系统栈可能溢出，这在C/C++里尤其明显。解决方案有两种，一是把递归改成显式栈的迭代法，用栈模拟后序遍历，在每个节点处记录当前深度；二是直接在遍历时多带一个参数depth，每下一层加1，维护一个全局最大值。这里不推荐用全局变量，因为多线程环境会有问题，用迭代法或传递参数更干净。

3.2 求二叉树的节点数、叶子数与第K层节点数

这几个操作和求深度几乎是一个模子刻出来的，关键也是设计好递归返回值：

• 节点总数：count = count(left) + count(right) + 1，左右子树节点数之和再加自己。
• 叶子节点数：如果当前节点左右孩子都为空，返回1；否则返回leafCount(left) + leafCount(right)。
• 第K层节点数：把“目标层数为根”作为基准，每次递归向下层数减1，直到K == 1时说明到达目标层，返回1，累加左边和右边。

这三个操作建议你全部手写一遍，写的时候体会一下：为什么有的递归需要“出口 + 两个分支”，有的只需要“出口 + 一个分支”。你会越来越明显感觉到，二叉树递归的“型”就是固定的，变化只在“当前节点要贡献什么”。

在工程层面，这类统计操作用递归已经足够，因为节点数再多也就在百万级别，递归深度受树高限制，不会特别深。真正要注意的是：别在递归里“重复递归”同一个子树，比如在某个分支里又对同一棵子树做一次完整统计，这样复杂度会上到O(n^2)。比如判断平衡二叉树，如果每个节点都调用一次求深度，就会出现这种重复计算，正确姿势是在递归返回结构体里同时携带深度和是否平衡，一趟走完所有事。

3.3 判断平衡二叉树与完全二叉树的三种模板

判断是不是平衡二叉树，定义很简单：每个节点左右子树高度差绝对值不超过1。但实现上，新手往往写出一个看似对、其实O(n^2)的版本：在遍历每个节点时都调用depth函数，结果每个节点都要往下探到底，整体复杂度一下就高了。

正确解法是“一边算深度一边判断”，在递归返回时带着深度值，如果发现某个子树不平衡，立即向上层返回一个标志。C语言里可以用返回值-1表示“该子树不平衡”，否则返回深度。这样每棵子树只被访问一次，整体复杂度是O(n)。这里我想额外说一点：很多时候面试官考察的不是你背没背过解法，而是你有没有意识到“计算过程中可以顺便维护额外信息”。这就是工程优化里常见的“一趟扫描代替多趟扫描”的思路。

判断完全二叉树则要用层序遍历。思路我前面提过：层序遍历过程中，遇到第一个空节点之后，如果后面还有非空节点，那这棵树就不是完全二叉树。实现时用一个标志位flag，初始为false；出队时若节点为空，置flag为true；若节点非空且flag已经为true，则直接判false。这个方法比递归做起来直观得多，也快。

4. 搜索二叉树与线索二叉树：两款特别能打的二叉树变体

搜索二叉树，也就是热词里的“搜索二叉树”，英文缩写叫BST，它的核心规则简单但威力巨大：任意节点的左子树所有值都小于它，右子树所有值都大于它。这个特性意味着，只要树是平衡的，每次查找都可以扔掉一半的候选范围，复杂度能做到O(log n)。搜索二叉树是后面几乎所有高级树结构（AVL、红黑树、B树）的基础，值得你花大力气吃透。

线索二叉树则是一个“空间换时间”的经典。普通二叉树有好多空指针：n个节点共有2n个指针域，实际只用了n-1个，剩下n+1个空指针全部浪费。线索二叉树把这些空指针利用起来，分别指向遍历序列中的前驱和后继节点，这样遍历的时候不需要递归或栈，直接顺着线索走即可。这是个很细的考点，面试出现的频率不算最高，但一旦问到就是考察你“是否真正理解指针的意义”。

4.1 搜索二叉树的查找与插入：一次行走的递归

BST的查找和数组二分查找本质是一回事，只不过载体从数组变成了树。从根出发，目标值比当前节点小就往左走，比当前节点大就往右走，相等就命中。整个过程就是一条从根到某个节点的路径，最坏情况是走到叶子还没有，树高就是最大比较次数。

插入的逻辑和查找几乎一致，也是从根出发，找到合适的位置挂上。区别在于插入前需要判断：如果当前节点为空，说明找到了插入点，直接新建节点返回；否则按大小比较，决定往左递归还是往右递归，然后把递归的返回值挂到当前的左或右指针上。这里有一个非常容易写错的地方：递归函数要返回更新后的子树根，否则你新建的节点挂不上树。很多新手写成“递归进去不接收返回值”，结果树还是原来的树，怎么插都插不进去。记住经验法则：凡是修改树结构的递归，基本都要带着返回值return newRoot，并把返回值赋值给父节点的对应指针。

BST的删除是三兄弟里最麻烦的，核心难点在于删除的节点可能有两个孩子。经典策略是：找到右子树中最小的节点来顶替被删节点的位置，或者用左子树最大的节点。这样能保证替换后仍然满足BST的定义。具体实现上，找右子树最小节点就是一个“一直往左走”的过程，再把那个节点的值赋给当前节点，然后递归删除右子树里的那个最小节点。这段逻辑看起来绕，但思路扎实，强烈建议在纸上画几个例子再写代码。

4.2 线索二叉树：把空指针变成“高速公路”

先说思路。线索二叉树要利用空指针：如果某个节点没有左孩子，就让它左指针指向“中序遍历时它的前驱节点”；如果没右孩子，就让它右指针指向“中序遍历时它的后继节点”。为了区分这个指针到底是原本的孩子指针，还是线索，每个节点还得加两个布尔位，比如ltag和rtag，0表示正常孩子，1表示线索。

线索化的过程本质上是在中序遍历的过程中完成的，用一个全局指针pre记录“上一个访问的节点”。当遍历到当前节点时，若它的左孩子为空，就把左指针指向pre，并设置ltag=1；若pre非空且它的右孩子为空，就把pre的右指针指向当前节点，设置rtag=1，然后更新pre为当前节点。这个“现场接线”的步骤非常考察你对遍历过程的理解，因为线索的顺序完全由遍历顺序决定。

为什么线索二叉树有实用价值？因为普通二叉树中序遍历必须先递归到最左子树，再一层层回来，这个过程需要栈；而线索化之后，你可以从第一个节点开始，通过右线索一路定位后继，直到结束，不需要任何栈和递归。这在“频繁需要遍历”的场景下，节省的时间和空间都很可观。不过线索二叉树也有代价：插入、删除节点时要维护线索，逻辑复杂度明显上升，所以工程上用得不多，更多出现在教材和考试里。

4.3 二叉树的应用场景：从超市货架到文件系统

很多人学数据结构会问“这玩意儿到底有啥用”，我特别喜欢用一个“超市货架”的例子来回答。假设超市里有数不清的商品，每个商品有货号。如果你用一个无序链表维护商品信息，找一个商品要遍历全表，顾客结账会慢到崩溃。但如果用BST存货号，每次查询可以砍半搜索，数据量大时差距立竿见影。这个例子对应热词里那个有趣的组合“超市货架 遍历二叉树”——货架的物理排列可以看作一层层节点，而管理系统的索引结构，底层就是一棵二叉搜索树。你用层序遍历的思想去巡检货架，从入口到最里排，先访问当前排，再处理左右通道，这和遍历二叉树的逻辑一模一样。

再往深了说，操作系统的文件目录就是一棵树；编译器的表达式解析会把“a+b*c”解析成语法树，这棵树也是二叉树形态；数据库的索引在MySQL里用的是B+树，但B+树本质上是对BST的扩展。包括很多AI算法里的决策树、随机森林，底层也是二叉树或基于二叉树的变体。学二叉树绝对不是学一个“象牙塔玩具”，它是你理解这些大工程的“扳手”。每当你觉得某样东西可以“二分”或“分层”去处理，二叉树的思想就能派上用场。

5. 写二叉树程序时为什么总是报运行时错误？排查实录

热词里那句“写二叉树程序时为什么总是报运行时错误”几乎是所有初学者都会经历的心酸。我当年刚开始练习二叉树，每次提交作业都提心吊胆，不是段错误，就是死循环。后来摸爬滚打久了，发现所有运行时错误其实都有规律，大概能分成几类。我先说结论：二叉树程序的运行时错误，十有八九跟“指针”和“递归出口”有关。

运行时错误在C/C++里最常见的就是“Segmentation fault”，翻译成人话就是你访问了一块不属于你的内存。放在二叉树里，最常见的场景就是对一个空指针取了字段，比如node->left，但是node其实是NULL。另一个高频错误是“栈溢出”，通常表现为程序没崩，但是一直不输出，或者直接卡死，这是因为递归没有正确的出口，或者递归一直都在拼接非空节点，导致栈无限增长。

5.1 空指针的问题：判空的位置和时机

空指针访问，是新手的头号杀手。我见过最典型的代码是这样：

if (node->left) { node = node->left; }

看起来好像已经判断了node->left不为空，但问题是你没有判断node本身是否为空。如果调用方传入了一个NULL根节点，那么一进来node->left就炸了。正确姿势是：函数入口处先做统一判空，然后才允许继续访问左孩子或者右孩子。另一个常见陷阱是：递归调用的返回结果没有检查。比如插入操作返回了新建的节点，但是父节点没有把返回值挂上去，下次你在空位置上取数据，照样段错误。

这里我要分享一个排查技巧：如果你用gdb，编译时加上-g选项，崩了之后用bt命令查看调用栈，栈上的函数名基本能帮你直接定位到哪一行出了问题。如果没有调试器，就在每层递归入口打印一条日志，输出当前节点的值，配合肉眼观察树的结构是哪里断层的。这个方法笨，但对于教学和初学阶段真的能治本，打印日志是人类理解递归最有效的手段。

5.2 递归没有退出条件：栈溢出与死循环

递归写多了，最容易犯的毛病就是“只剩进，没有出”。比如你想写一个遍历所有节点的函数，但是出口条件写成了node->left == NULL && node->right == NULL，这可能导向死循环吗？不一定死循环，但会漏树。更严重的案例是：递归出口写的是node != NULL才返回，却在某一路径上递归调用时没有改变参数，比如traverse(node)永远传同一个节点，这就成了无限递归，栈会越叠越高，最终程序崩溃。

排查是否死于栈溢出，最直接的方法是看崩溃时的错误信息。类Unix系统下，栈溢出通常会显示“Segmentation fault”而不是正常的返回；Windows下会弹“stack overflow”之类的提示。在代码层面，你可以先加一个全局计数器，每次递归进来加1，如果数字飙升到几万还没停，就能断定是出口有问题。这个方法虽然傻，但在没有复杂工具辅助时尤其好用。

还要强调一个容易被忽略的点：C语言的递归和系统栈相关，默认栈空间不大，一般Linux是8MB左右。一棵退化严重的斜树，如果深度到了几十万层，即便你的递归逻辑完全正确，也一样会栈溢出。这时候就得改用显式栈的迭代写法，或者考虑换成中序遍历的双栈法。这是工程思维和考试思维最大的不同：考试默认不用考虑栈深度，工程中要重视。

5.3 返回值用错：修改树结构后没有接住新根

这个错误在高频热词里不太显眼，但我作为一个看过无数人摔跟头的过来人，必须单拎出来说一说。很多二叉树的修改操作，比如插入节点、删除节点、旋转调整，递归函数的返回都是“修改后的子树根”。如果主调方不接住这个返回值，那树就白改了。

举一个插入节点的典型错误写法：

void insertNode(TreeNode* root, int val) { if (root == NULL) { root = createNode(val); // 这里确实新建了节点 } else if (val < root->val) { insertNode(root->left, val); // 但返回值没人接！ } else { insertNode(root->right, val); } }

这段代码看起来逻辑完美，但运行完你会惊讶地发现树根本没变。原因在于：root = createNode(val)只修改了局部变量的root，并没有把它挂到上一层的左指针或右指针上；递归进去的root->left传递的是值的拷贝，即使内部改了，外面也不知道。正确的写法是：

TreeNode* insertNode(TreeNode* root, int val) { if (root == NULL) return createNode(val); if (val < root->val) { root->left = insertNode(root->left, val); } else { root->right = insertNode(root->right, val); } return root; }

看到区别了吗？所有递归调用都有返回值，并且都赋值给了父节点的相应指针。这可能比你想象的重要得多。建议你写任何“会改变树结构”的递归时，第一句话先问自己：这个递归函数返回的是什么？主调方有没有把它接住？这两个问题想清楚，至少能少踩一半的二叉树运行时错误。

5.4 常见问题排查速查表

为了方便你对照自查，我把二叉树程序最常见的运行时错误整理成了一张表，基本涵盖初学者遇到的所有典型情况。

这张表的左侧是现象，右侧是排查方向。实际遇到问题的时候，先想清楚“它是指针问题还是递归问题”，再去翻对应代码，效率会高很多。很多人在二叉树程序上耗时太久，不是代码能力不足，而是排查方式太随机，没有体系。有了这个表，你至少能少走一半的弯路。

6. 最后再分享几个写二叉树代码的个人习惯

写到最后，我想聊几个我自己的个人习惯。这些东西不算什么高深理论，纯粹是踩过坑之后养成的肌肉记忆，但确实让我的二叉树代码比以前稳很多。

第一个习惯是，任何涉及指针操作的地方，先问“这个指针可能为空吗”。不管是入口参数、左孩子、右孩子，还是递归调用的返回结果，只要有一丝可能为空，就统一处理。写代码的时候可以多写几个防空的if，写完再回头看看有没有冗余，这是“先求对再求美”的思路，比一次性追求简洁要可靠得多。特别是C语言这种没有自动垃圾回收和空指针安全的语言，判空永远不过分。

第二个习惯是，结构体里总是额外带一个计数器或者层次字段。比如我在调试二叉树的深度时，经常临时给节点结构体加一个int depth字段，在插入时维护深度信息，这样查起来就少很多递归调用的麻烦。虽然正式代码里不一定要带，但调试阶段这些“冗余字段”能救命。等程序稳定了，再决定哪些字段该留下，哪些该删掉。

第三个习惯更实用：凡是写递归，我都先在注释里写清楚“当前节点要做什么、左子树返回什么、右子树返回什么”。先写注释再写代码，比先写代码再补注释，出错率低得多。尤其是那些返回值类型是“子树根”的递归，如果没有事先想清楚返回语义，很容易写出一半截逻辑。

另外我想特别说一句关于学习路径的话。如果你正在自学二叉树，别指望看一遍教程就能打通所有题目。我当年是每天挑几道LeetCode上的简单题反复刷，从求深度、求节点数、层序遍历、翻转二叉树这四道题开始，刷到滚瓜烂熟，后面很多题自然就通了。二叉树这个知识点的特点是，它太依赖“手感”，只看不做永远隔着一层纱。你亲手写过一遍层序遍历的队列实现，再遇到“按层分组输出”就不会发怵；你被段错误折磨过一次，以后写任何树的代码都会条件反射先判空。

如果还要再给一条建议的话，那就是：学着在纸上画递归展开的过程。遇到复杂的题目，比如“最近公共祖先”“路径总和”，不要急着在电脑前硬调，先在草稿纸上把一棵三层的二叉树画出来，逐步模拟每个节点在递归过程里经历了什么。这个习惯能帮你真正建立递归的直觉，而且对面试时的沟通表达也有很大帮助。二叉树的精巧之处，就在于它用朴素的结构托起了一整个计算机科学的世界，值得你静下心来，慢慢消化。