作为一个常年跟数据结构打交道的人我越来越觉得二叉树是个很有意思的话题。很多初学者觉得它难无非是递归绕不过来、指针指来指去就晕了。但你真把二叉树吃透了后面学红黑树、B树、堆排序都会觉得顺理成章。这篇“13二叉树3”是系列第三篇重点不是再念一遍概念而是把遍历、深度、搜索树、线索树这些核心知识点揉碎了讲再附带聊聊那些让新手崩溃的运行时错误到底是怎么来的。如果你是正在备战面试的应届生、刚学到树的在校生或者工作中需要用二叉树但一直没系统梳理过的开发者这篇文章应该能帮你把零散的知识点串成一条线。我会结合大量实操经验把“为什么这么写”“为什么报错”讲透而不是简单丢一堆代码让你背。1. 为什么要学二叉树从“线性世界”到“分支世界”1.1 二叉树解决了什么问题数组、链表这些线性结构最大的问题在于“一条道走到黑”。你想在链表里找一个元素只能从头开始一个个比时间复杂度是O(n)。数组虽然能用二分查找达到O(log n)但前提是数据必须有序而且插入删除要移动大量元素代价很高。二叉树不一样。它让数据有了“分岔路口”每个节点最多有两个分支左和右。这种结构天生适合“分而治之”的思路每次比较都能排除一半的子树查找效率能做到O(log n)。更重要的是树形结构还能表达层级关系比如文件系统、公司组织架构、表达式解析这些用线性结构根本没法优雅地建模。我一直喜欢用一个类比线性结构像一本只有目录没有章节跳转的书你得一页页翻二叉树像一本带智能索引的书每次翻页都能告诉你“目标在前半本还是后半本”。你能感受到那种“选择分支”的爽快感这就是树的核心魅力。1.2 几个核心概念一次说清很多教材喜欢一上来就堆术语搞得人头晕。我帮你把这些概念跟实际代码对应起来看。节点树的基本单元存一个数据值再加两个指针左孩子、右孩子。在C/C里通常这么定义typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;根节点整棵树最顶层的那个节点没有父节点。一棵树只有一个根。叶子节点没有孩子节点的节点也就是left和right都是NULL。深度从根节点到某个节点的路径长度。根节点的深度是0有的教材定义为1看你习惯但写代码时要保持一致。高度从某个节点到最远叶子节点的路径长度。整棵树的高度等于根节点的高度。这里特别提醒一下深度和高度是反着数的。深度是从上往下数高度是从下往上数。很多bug就是因为把这两个概念搞混了导致递归的终止条件写错。简单记求深度用depth max(leftDepth, rightDepth) 1这个公式你看一眼就明白因为根节点自己算一层加上子树的最大深度就行。1.3 二叉树的存储方式链式还是顺序多数教程默认用链式存储也就是上面那种带指针的节点。但在实际刷题和应用里顺序存储也很常见尤其适合完全二叉树。顺序存储就是把树的节点按层序放进数组下标从0开始。对于下标为i的节点它的左孩子下标是2*i1右孩子是2*i2父节点是(i-1)/2。这公式很实用。比如堆排序用的就是顺序存储的完全二叉树不需要任何指针纯数组就能表达树结构。链式存储的好处是灵活任意形态的树都能存不会浪费空间。坏处是每个节点都要额外的两个指针空间对于节点很多但分支很少的树比如斜树内存利用率不高。做项目时我的选择标准很简单如果树的结构固定、接近完全二叉树用数组如果是动态插入删除、形态不可控用链式。面试中九成题目都是用链式因为操作起来更直观也更能考察你对指针和递归的理解。2. 二叉树的遍历前序、中序、后序与层序2.1 三种深度优先遍历的递归实现遍历是二叉树最基础的操作没有之一。所谓“前序、中序、后序”区别就在于访问根节点的时机。前序根 - 左 - 右。先处理当前节点再递归处理左子树和右子树。中序左 - 根 - 右。先处理左子树再处理当前节点最后处理右子树。后序左 - 右 - 根。先处理完所有子树最后才轮到根节点。递归代码非常简洁以中序为例void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); }前序和后序只是把printf那行换个位置。很多人觉得递归难是因为老想“展开”每一步。其实你只需要相信两件事第一递归函数能做对子树的处理第二终止条件到了就回头。把这两点想清楚递归就是套公式。这里有个初学者容易忽略的点中序遍历一颗二叉搜索树得到的结果是有序的。这个性质在面试里经常考比如“验证一棵树是否是二叉搜索树”最直接的思路就是中序遍历后检查序列是否递增。2.2 非递归遍历为什么面试爱考递归写起来爽但真正跑在大数据量上会出问题——函数调用栈有深度限制树深了容易栈溢出。所以非递归遍历是必须掌握的。非递归前序和中序需要显式地用一个栈来模拟系统调用栈。以中序为例核心逻辑是一路往左走把经过的节点全部压栈走到NULL了弹出栈顶访问然后转向右子树。void inorderIterative(TreeNode *root) { Stack *s createStack(); TreeNode *cur root; while (cur ! NULL || !isEmpty(s)) { while (cur ! NULL) { push(s, cur); cur cur-left; } cur pop(s); printf(%d , cur-val); cur cur-right; } }后序非递归难度高一些因为根节点最后访问你需要在弹出时判断“右子树是否已经访问过了”。常用的做法有两个一是给节点加一个visited标记二是用一个prev指针记录上一个访问的节点如果prev是当前节点的右孩子说明右子树访问完了可以访问当前节点。面试时如果时间紧张我建议至少把前序和中序的非递归写熟后序可以记一个“前序的变体”技巧先按“根-右-左”访问再把结果反转就得到了“左-右-根”。这个技巧实测好用代码量也小。2.3 层序遍历队列的经典应用深度优先遍历用栈或递归广度优先遍历层序用队列。层序的逻辑是从根节点开始每访问一个节点就把它的左右孩子放入队列尾部然后从队列头部取出下一个节点继续访问。void levelOrder(TreeNode *root) { if (root NULL) return; Queue *q createQueue(); enqueue(q, root); while (!isEmpty(q)) { TreeNode *node dequeue(q); printf(%d , node-val); if (node-left) enqueue(q, node-left); if (node-right) enqueue(q, node-right); } }层序遍历的变体也很常见按层输出每层一行。做法是在while循环里先记录当前队列的长度size然后只处理size个节点这size个节点就是同一层的。这个技巧在“二叉树右视图”“之字形打印”这类题目中频繁使用建议练熟。3. 二叉树的深度从递归到优化3.1 最大深度与最小深度求最大深度可能是二叉树递归里最常见的题目了。代码极其简单int maxDepth(TreeNode *root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }逻辑就是一棵树的最大深度等于左子树和右子树最大深度的较大值加上根节点这一层。这个“分而治之”的思路贯穿二叉树的所有递归问题务必彻底理解。最小深度则有个坑。很多人照着最大深度改写成return (leftDepth rightDepth ? leftDepth : rightDepth) 1结果遇到斜树就错了。比如根节点只有左子树没有右子树时右子树的深度是0取min会返回011这明显不对——因为右子树根本不存在谈不上深度。正确的做法是如果左子树为空返回右子树的深度1如果右子树为空返回左子树的深度1如果都不为空才取较小值。这种“看起来很简单但边界条件容易出错”的问题正是运行时错误的重灾区。我后面会详细展开。3.2 判断平衡二叉树平衡二叉树的定义是任意节点的左右子树高度差不超过1。注意是“任意节点”不是只有根节点。所以判断函数需要同时完成两件事返回子树的高度并告诉上层这棵子树是否平衡。网上有个经典解法是自顶向下每个节点都调一次高度计算时间复杂度O(n^2)。更好的做法是自底向上int checkBalance(TreeNode *root) { if (root NULL) return 0; int leftHeight checkBalance(root-left); if (leftHeight -1) return -1; int rightHeight checkBalance(root-right); if (rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return (leftHeight rightHeight ? leftHeight : rightHeight) 1; }返回-1就代表不平衡。这样每个节点只访问一次时间复杂度O(n)。我特别喜欢这个写法因为它把“高度计算”和“平衡判断”合二为一代码清晰还高效。3.3 深度相关问题的共同套路说句实话二叉树深度相关的问题翻来覆去就那么几个套路。求深度、高度递归后序遍历。判断平衡、对称、相同递归同时遍历多棵树或多节点。路径和、最大路径和递归返回值根据题目定义灵活设计。刷题多了你会发现递归函数的返回值设计是核心。是返回子树的高度还是返回布尔值还是返回该子树对父节点的最大贡献值想清楚这个代码就不容易写歪。我建议每次写递归前先明确回答三个问题这个函数干什么参数是什么返回值是什么回答完了再动手比你边写边猜要快得多。4. 写二叉树程序时为什么总是报运行时错误4.1 空指针最常见的崩溃原因我要说句直白的二叉树程序的运行时错误八成以上是空指针访问。初学者最常见的写法是这样void traverse(TreeNode *root) { printf(%d , root-val); // root可能为NULL traverse(root-left); traverse(root-right); }看起来没毛病但root传到叶子节点时它的left和right都是NULL下一层递归里root就是NULL直接访问root-val必然崩溃。解决办法就是在函数入口判断void traverse(TreeNode *root) { if (root NULL) return; printf(%d , root-val); traverse(root-left); traverse(root-right); }这个if (root NULL) return;就是二叉树递归的“安全气囊”。我见过太多人写得飞快却漏了这行然后花半小时调试。那怎么快速定位用调试器看调用栈你会发现崩在最深层的那次递归root确实是NULL然后一检查就是没写终止条件。还有一个容易踩坑的地方访问root-left前不检查root本身是否为NULL。比如写root-left-val如果root是NULL同样崩。安全做法是先用一个临时指针接住root-left判断不是NULL再继续。4.2 递归栈溢出当二叉树退化成链表递归虽然好写但每层递归都要占用栈空间深度太大就栈溢出了。很多人一听到“栈溢出”就以为是代码死循环其实更常见的原因是树本身太深。什么情况树会太深比如你往二叉搜索树里按顺序插入5、4、3、2、1树就会变成一条链深度等于节点数。如果节点有1万个递归深度就1万层系统栈肯定受不了。这种树叫斜树是平衡二叉树的“反面教材”。一句话总结递归适合深度可控的树或者面试时为了展示思路清晰工程上如果树可能很深一定要写非递归版本或者用自带栈的迭代方式。4.3 边界条件与代码习惯我第一次写二叉树程序时总报错后来把所有错误归了类发现无非几个原因建树时指针没初始化。TreeNode *node malloc(sizeof(TreeNode));之后必须让node-left node-right NULL;否则指针是野指针后面判断NULL就失效了。遍历时左右孩子混了。二叉树的“左”是有顺序的调换了位置前序中序就全乱了。插入节点时没有更新父节点的指向。比如只new了节点忘了接到parent-left或parent-right上树就连不起来。全局变量或静态变量没重置。多组测试用例共用同一个程序时静态变量会保留上一次的脏数据。这些坑的共性是代码逻辑本身没问题但内存状态不对。我建议凡是动态创建节点的操作一定要做到“创建即初始化用完即指NULL”。这不是强迫症这是二叉树程序稳定运行的基本素养。4.4 常见运行时错误速查表放到一张表里方便你排查报错类型常见原因快速排查方法空指针崩溃递归没写终止条件检查函数入口处if (root NULL) return;野指针崩溃节点指针未初始化创建节点后立即让left/right指向NULL栈溢出/Segmentation Fault树退化成链、递归过深改用非递归遍历或检查插入逻辑结果顺序不对前中后序访问顺序写错对照定义确认根节点访问时机死循环指针指回了祖先节点检查插入操作是否成环画图验证数据被覆盖多次构建树时未释放旧树每轮测试前调用清空函数我建议你在本地跑测试时开AddressSanitizer或者Valgrind它能直接告诉你哪一行访问了非法内存。这个习惯一旦养成排查这类问题的效率翻倍。5. 搜索二叉树有序性的威力5.1 BST的查找、插入与删除二叉搜索树BSTBinary Search Tree是二叉树最重要的应用之一。性质就一条左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。注意是所有不是直接的孩子。查找代码很自然TreeNode* searchBST(TreeNode *root, int target) { if (root NULL || root-val target) return root; if (target root-val) return searchBST(root-left, target); else return searchBST(root-right, target); }每次比较都把搜索范围砍半平均时间复杂度O(log n)。插入逻辑类似从根开始往左或往右走到空位就停下来挂上节点。难点在于删除因为要分三种情况删除叶子节点直接删父节点的孩子指针置NULL。删除只有一个孩子的节点用孩子接替被删节点。删除有两个孩子的节点经典做法是找到右子树的最小节点或左子树的最大节点用它的值覆盖被删节点再删除那个最小节点。第三种情况代码稍长但思路很固定。我建议你自己画一棵树手动模拟一遍删除过程比背十遍代码都管用。5.2 BST的退化问题与平衡思路BST有个致命弱点如果数据是近似有序插入的树就会严重失衡退化成链表所有操作退化为O(n)。这是面试必问的“为什么需要平衡二叉树”的答案。解决方案有很多方向AVL树通过旋转保持严格平衡红黑树通过颜色标记和局部调整保证近似平衡B树/B树通过多路分支降低树高。它们的本质都一样——用规则限制树的高度让查找永远维持在O(log n)左右。我给你的学习建议是先彻底搞懂BST的删除和“验证BST”这个题目再去看旋转操作。旋转是AVL的灵魂而AVL的旋转是后续理解红黑树、跳表的基础。旋转没有玄学就是“重新连接指针”捋一遍就通了。6. 线索二叉树把空指针利用起来6.1 为什么需要线索化你有没有想过一棵有n个节点的二叉树大约有n1个空指针这是怎么算的每个节点有两个指针共2n个每个非根节点都有一个父节点指向它所以有n-1个非空指针空指针就是2n - (n-1) n1个。这些空指针全放着不用挺浪费。线索二叉树的核心思想把这些空指针利用起来让它们指向遍历序列中的前驱或后继节点。这样遍历就不需要递归或栈了直接顺着线索走就行空间复杂度O(1)。这个思路在嵌入式开发、内存受限场景下特别实用。6.2 线索化的核心思路线索化要区分左指针和右指针原本是孩子还是前驱/后继。所以节点定义要加两个标记位typedef struct ThreadNode { int val; struct ThreadNode *left, *right; int leftTag; // 0表示左孩子1表示前驱 int rightTag; // 0表示右孩子1表示后继 } ThreadNode;线索化的过程本质上是一次遍历在遍历过程中记录“上一个访问的节点”pre。当当前节点的左孩子为空时让左指针指向上一个访问的节点前驱当pre的右孩子为空时让它的右指针指向当前节点后继。这里的关键是“当前节点访问时看左”而“前驱节点看右”顺序容易搞混建议画图辅助记忆。中序线索化最常用因为中序的“左-根-右”顺序恰好让线索化后的遍历非常自然。前序和后序线索化也有应用但后序线索化的实现更绕实际用得少。6.3 遍历线索二叉树线索化之后遍历就没那么烧脑了。以中序为例void inorderThreaded(ThreadNode *root) { if (root NULL) return; while (root-leftTag 0) { root root-left; // 找到最左节点 } while (root ! NULL) { printf(%d , root-val); if (root-rightTag 1) { root root-right; // 直接走后继线索 } else { root root-right; // 有右孩子转去右子树找最左节点 while (root ! NULL root-leftTag 0) { root root-left; } } } }第一次看可能有点晕但你跟着一个简单的树走一遍就明白了第一步先一路向左找到中序第一个节点之后每个节点如果右标志是1直接跳后继不是1就转向右子树再一路向左找最左节点。这个“两步循环”就是线索二叉树遍历的全部秘密。如果你只是应付考试或面试线索二叉树一般考概念和理解手写完整线索化代码的情况不多。但你要是做嵌入式或者追求极致空间利用的工作这个思想值得好好掌握。7. 写在最后二叉树学习的几个实操建议7.1 画图是解决问题的第一工具我每次调试二叉树程序第一件事不是看代码是画图。拿一张纸或者用白板把树画出来把指针变化标出来。就是这么土的办法能解决我八成以上的困惑。特别是递归问题很多人的困境是“代码能跑但不知道为啥对”。这时候画一棵小树手动模拟递归的调用过程走两遍就通了。我至今保留着画树梳理递归的习惯强烈推荐你也试试。别高看自己的脑内模拟能力写下来更靠谱。7.2 做题和工程应用要分开在校刷题或者面试时递归版遍历完全够用代码短、逻辑清晰面试官也爱看。但到了工程项目里数据量一大递归栈溢出就是真事故了。所以我的建议是两种写法都要会并且要能说清楚各自的适用场景。你可以先写递归版本跑通逻辑再改成迭代版本验证结果这样就同时掌握了两套写法。7.3 把“空指针检查”焊死在脑子里说句掏心窝的二叉树程序出bug绝大多数不是算法不懂就是指针没管好。我在项目里见过太多因为漏掉一个NULL判断导致线上服务半夜崩掉的案例。不要觉得“这个节点肯定不为空”你要相信运行时的一切可能。写代码时无脑加上if (node ! NULL)这种守卫不会损失性能但能省掉大量调试时间。学二叉树就像学骑车理论讲再多不如自己骑两圈。把这篇文章里提到的代码都手敲一遍敲的时候思考一下root为NULL会发生什么再自己画几棵树模拟一下遍历过程。等你熟练了再看后续的AVL、红黑树、B树会觉得整个世界都顺了。希望这些内容对你有实际帮助也欢迎你在自己的项目里大胆用起来。 
长河君 · 2026/10/11 5:39:37 · 阅读 1.2k 二叉树详解：从遍历、深度到搜索树与线索树
作为一个常年跟数据结构打交道的人我越来越觉得二叉树是个很有意思的话题。很多初学者觉得它难无非是递归绕不过来、指针指来指去就晕了。但你真把二叉树吃透了后面学红黑树、B树、堆排序都会觉得顺理成章。这篇“13二叉树3”是系列第三篇重点不是再念一遍概念而是把遍历、深度、搜索树、线索树这些核心知识点揉碎了讲再附带聊聊那些让新手崩溃的运行时错误到底是怎么来的。如果你是正在备战面试的应届生、刚学到树的在校生或者工作中需要用二叉树但一直没系统梳理过的开发者这篇文章应该能帮你把零散的知识点串成一条线。我会结合大量实操经验把“为什么这么写”“为什么报错”讲透而不是简单丢一堆代码让你背。1. 为什么要学二叉树从“线性世界”到“分支世界”1.1 二叉树解决了什么问题数组、链表这些线性结构最大的问题在于“一条道走到黑”。你想在链表里找一个元素只能从头开始一个个比时间复杂度是O(n)。数组虽然能用二分查找达到O(log n)但前提是数据必须有序而且插入删除要移动大量元素代价很高。二叉树不一样。它让数据有了“分岔路口”每个节点最多有两个分支左和右。这种结构天生适合“分而治之”的思路每次比较都能排除一半的子树查找效率能做到O(log n)。更重要的是树形结构还能表达层级关系比如文件系统、公司组织架构、表达式解析这些用线性结构根本没法优雅地建模。我一直喜欢用一个类比线性结构像一本只有目录没有章节跳转的书你得一页页翻二叉树像一本带智能索引的书每次翻页都能告诉你“目标在前半本还是后半本”。你能感受到那种“选择分支”的爽快感这就是树的核心魅力。1.2 几个核心概念一次说清很多教材喜欢一上来就堆术语搞得人头晕。我帮你把这些概念跟实际代码对应起来看。节点树的基本单元存一个数据值再加两个指针左孩子、右孩子。在C/C里通常这么定义typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;根节点整棵树最顶层的那个节点没有父节点。一棵树只有一个根。叶子节点没有孩子节点的节点也就是left和right都是NULL。深度从根节点到某个节点的路径长度。根节点的深度是0有的教材定义为1看你习惯但写代码时要保持一致。高度从某个节点到最远叶子节点的路径长度。整棵树的高度等于根节点的高度。这里特别提醒一下深度和高度是反着数的。深度是从上往下数高度是从下往上数。很多bug就是因为把这两个概念搞混了导致递归的终止条件写错。简单记求深度用depth max(leftDepth, rightDepth) 1这个公式你看一眼就明白因为根节点自己算一层加上子树的最大深度就行。1.3 二叉树的存储方式链式还是顺序多数教程默认用链式存储也就是上面那种带指针的节点。但在实际刷题和应用里顺序存储也很常见尤其适合完全二叉树。顺序存储就是把树的节点按层序放进数组下标从0开始。对于下标为i的节点它的左孩子下标是2*i1右孩子是2*i2父节点是(i-1)/2。这公式很实用。比如堆排序用的就是顺序存储的完全二叉树不需要任何指针纯数组就能表达树结构。链式存储的好处是灵活任意形态的树都能存不会浪费空间。坏处是每个节点都要额外的两个指针空间对于节点很多但分支很少的树比如斜树内存利用率不高。做项目时我的选择标准很简单如果树的结构固定、接近完全二叉树用数组如果是动态插入删除、形态不可控用链式。面试中九成题目都是用链式因为操作起来更直观也更能考察你对指针和递归的理解。2. 二叉树的遍历前序、中序、后序与层序2.1 三种深度优先遍历的递归实现遍历是二叉树最基础的操作没有之一。所谓“前序、中序、后序”区别就在于访问根节点的时机。前序根 - 左 - 右。先处理当前节点再递归处理左子树和右子树。中序左 - 根 - 右。先处理左子树再处理当前节点最后处理右子树。后序左 - 右 - 根。先处理完所有子树最后才轮到根节点。递归代码非常简洁以中序为例void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); }前序和后序只是把printf那行换个位置。很多人觉得递归难是因为老想“展开”每一步。其实你只需要相信两件事第一递归函数能做对子树的处理第二终止条件到了就回头。把这两点想清楚递归就是套公式。这里有个初学者容易忽略的点中序遍历一颗二叉搜索树得到的结果是有序的。这个性质在面试里经常考比如“验证一棵树是否是二叉搜索树”最直接的思路就是中序遍历后检查序列是否递增。2.2 非递归遍历为什么面试爱考递归写起来爽但真正跑在大数据量上会出问题——函数调用栈有深度限制树深了容易栈溢出。所以非递归遍历是必须掌握的。非递归前序和中序需要显式地用一个栈来模拟系统调用栈。以中序为例核心逻辑是一路往左走把经过的节点全部压栈走到NULL了弹出栈顶访问然后转向右子树。void inorderIterative(TreeNode *root) { Stack *s createStack(); TreeNode *cur root; while (cur ! NULL || !isEmpty(s)) { while (cur ! NULL) { push(s, cur); cur cur-left; } cur pop(s); printf(%d , cur-val); cur cur-right; } }后序非递归难度高一些因为根节点最后访问你需要在弹出时判断“右子树是否已经访问过了”。常用的做法有两个一是给节点加一个visited标记二是用一个prev指针记录上一个访问的节点如果prev是当前节点的右孩子说明右子树访问完了可以访问当前节点。面试时如果时间紧张我建议至少把前序和中序的非递归写熟后序可以记一个“前序的变体”技巧先按“根-右-左”访问再把结果反转就得到了“左-右-根”。这个技巧实测好用代码量也小。2.3 层序遍历队列的经典应用深度优先遍历用栈或递归广度优先遍历层序用队列。层序的逻辑是从根节点开始每访问一个节点就把它的左右孩子放入队列尾部然后从队列头部取出下一个节点继续访问。void levelOrder(TreeNode *root) { if (root NULL) return; Queue *q createQueue(); enqueue(q, root); while (!isEmpty(q)) { TreeNode *node dequeue(q); printf(%d , node-val); if (node-left) enqueue(q, node-left); if (node-right) enqueue(q, node-right); } }层序遍历的变体也很常见按层输出每层一行。做法是在while循环里先记录当前队列的长度size然后只处理size个节点这size个节点就是同一层的。这个技巧在“二叉树右视图”“之字形打印”这类题目中频繁使用建议练熟。3. 二叉树的深度从递归到优化3.1 最大深度与最小深度求最大深度可能是二叉树递归里最常见的题目了。代码极其简单int maxDepth(TreeNode *root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }逻辑就是一棵树的最大深度等于左子树和右子树最大深度的较大值加上根节点这一层。这个“分而治之”的思路贯穿二叉树的所有递归问题务必彻底理解。最小深度则有个坑。很多人照着最大深度改写成return (leftDepth rightDepth ? leftDepth : rightDepth) 1结果遇到斜树就错了。比如根节点只有左子树没有右子树时右子树的深度是0取min会返回011这明显不对——因为右子树根本不存在谈不上深度。正确的做法是如果左子树为空返回右子树的深度1如果右子树为空返回左子树的深度1如果都不为空才取较小值。这种“看起来很简单但边界条件容易出错”的问题正是运行时错误的重灾区。我后面会详细展开。3.2 判断平衡二叉树平衡二叉树的定义是任意节点的左右子树高度差不超过1。注意是“任意节点”不是只有根节点。所以判断函数需要同时完成两件事返回子树的高度并告诉上层这棵子树是否平衡。网上有个经典解法是自顶向下每个节点都调一次高度计算时间复杂度O(n^2)。更好的做法是自底向上int checkBalance(TreeNode *root) { if (root NULL) return 0; int leftHeight checkBalance(root-left); if (leftHeight -1) return -1; int rightHeight checkBalance(root-right); if (rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return (leftHeight rightHeight ? leftHeight : rightHeight) 1; }返回-1就代表不平衡。这样每个节点只访问一次时间复杂度O(n)。我特别喜欢这个写法因为它把“高度计算”和“平衡判断”合二为一代码清晰还高效。3.3 深度相关问题的共同套路说句实话二叉树深度相关的问题翻来覆去就那么几个套路。求深度、高度递归后序遍历。判断平衡、对称、相同递归同时遍历多棵树或多节点。路径和、最大路径和递归返回值根据题目定义灵活设计。刷题多了你会发现递归函数的返回值设计是核心。是返回子树的高度还是返回布尔值还是返回该子树对父节点的最大贡献值想清楚这个代码就不容易写歪。我建议每次写递归前先明确回答三个问题这个函数干什么参数是什么返回值是什么回答完了再动手比你边写边猜要快得多。4. 写二叉树程序时为什么总是报运行时错误4.1 空指针最常见的崩溃原因我要说句直白的二叉树程序的运行时错误八成以上是空指针访问。初学者最常见的写法是这样void traverse(TreeNode *root) { printf(%d , root-val); // root可能为NULL traverse(root-left); traverse(root-right); }看起来没毛病但root传到叶子节点时它的left和right都是NULL下一层递归里root就是NULL直接访问root-val必然崩溃。解决办法就是在函数入口判断void traverse(TreeNode *root) { if (root NULL) return; printf(%d , root-val); traverse(root-left); traverse(root-right); }这个if (root NULL) return;就是二叉树递归的“安全气囊”。我见过太多人写得飞快却漏了这行然后花半小时调试。那怎么快速定位用调试器看调用栈你会发现崩在最深层的那次递归root确实是NULL然后一检查就是没写终止条件。还有一个容易踩坑的地方访问root-left前不检查root本身是否为NULL。比如写root-left-val如果root是NULL同样崩。安全做法是先用一个临时指针接住root-left判断不是NULL再继续。4.2 递归栈溢出当二叉树退化成链表递归虽然好写但每层递归都要占用栈空间深度太大就栈溢出了。很多人一听到“栈溢出”就以为是代码死循环其实更常见的原因是树本身太深。什么情况树会太深比如你往二叉搜索树里按顺序插入5、4、3、2、1树就会变成一条链深度等于节点数。如果节点有1万个递归深度就1万层系统栈肯定受不了。这种树叫斜树是平衡二叉树的“反面教材”。一句话总结递归适合深度可控的树或者面试时为了展示思路清晰工程上如果树可能很深一定要写非递归版本或者用自带栈的迭代方式。4.3 边界条件与代码习惯我第一次写二叉树程序时总报错后来把所有错误归了类发现无非几个原因建树时指针没初始化。TreeNode *node malloc(sizeof(TreeNode));之后必须让node-left node-right NULL;否则指针是野指针后面判断NULL就失效了。遍历时左右孩子混了。二叉树的“左”是有顺序的调换了位置前序中序就全乱了。插入节点时没有更新父节点的指向。比如只new了节点忘了接到parent-left或parent-right上树就连不起来。全局变量或静态变量没重置。多组测试用例共用同一个程序时静态变量会保留上一次的脏数据。这些坑的共性是代码逻辑本身没问题但内存状态不对。我建议凡是动态创建节点的操作一定要做到“创建即初始化用完即指NULL”。这不是强迫症这是二叉树程序稳定运行的基本素养。4.4 常见运行时错误速查表放到一张表里方便你排查报错类型常见原因快速排查方法空指针崩溃递归没写终止条件检查函数入口处if (root NULL) return;野指针崩溃节点指针未初始化创建节点后立即让left/right指向NULL栈溢出/Segmentation Fault树退化成链、递归过深改用非递归遍历或检查插入逻辑结果顺序不对前中后序访问顺序写错对照定义确认根节点访问时机死循环指针指回了祖先节点检查插入操作是否成环画图验证数据被覆盖多次构建树时未释放旧树每轮测试前调用清空函数我建议你在本地跑测试时开AddressSanitizer或者Valgrind它能直接告诉你哪一行访问了非法内存。这个习惯一旦养成排查这类问题的效率翻倍。5. 搜索二叉树有序性的威力5.1 BST的查找、插入与删除二叉搜索树BSTBinary Search Tree是二叉树最重要的应用之一。性质就一条左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。注意是所有不是直接的孩子。查找代码很自然TreeNode* searchBST(TreeNode *root, int target) { if (root NULL || root-val target) return root; if (target root-val) return searchBST(root-left, target); else return searchBST(root-right, target); }每次比较都把搜索范围砍半平均时间复杂度O(log n)。插入逻辑类似从根开始往左或往右走到空位就停下来挂上节点。难点在于删除因为要分三种情况删除叶子节点直接删父节点的孩子指针置NULL。删除只有一个孩子的节点用孩子接替被删节点。删除有两个孩子的节点经典做法是找到右子树的最小节点或左子树的最大节点用它的值覆盖被删节点再删除那个最小节点。第三种情况代码稍长但思路很固定。我建议你自己画一棵树手动模拟一遍删除过程比背十遍代码都管用。5.2 BST的退化问题与平衡思路BST有个致命弱点如果数据是近似有序插入的树就会严重失衡退化成链表所有操作退化为O(n)。这是面试必问的“为什么需要平衡二叉树”的答案。解决方案有很多方向AVL树通过旋转保持严格平衡红黑树通过颜色标记和局部调整保证近似平衡B树/B树通过多路分支降低树高。它们的本质都一样——用规则限制树的高度让查找永远维持在O(log n)左右。我给你的学习建议是先彻底搞懂BST的删除和“验证BST”这个题目再去看旋转操作。旋转是AVL的灵魂而AVL的旋转是后续理解红黑树、跳表的基础。旋转没有玄学就是“重新连接指针”捋一遍就通了。6. 线索二叉树把空指针利用起来6.1 为什么需要线索化你有没有想过一棵有n个节点的二叉树大约有n1个空指针这是怎么算的每个节点有两个指针共2n个每个非根节点都有一个父节点指向它所以有n-1个非空指针空指针就是2n - (n-1) n1个。这些空指针全放着不用挺浪费。线索二叉树的核心思想把这些空指针利用起来让它们指向遍历序列中的前驱或后继节点。这样遍历就不需要递归或栈了直接顺着线索走就行空间复杂度O(1)。这个思路在嵌入式开发、内存受限场景下特别实用。6.2 线索化的核心思路线索化要区分左指针和右指针原本是孩子还是前驱/后继。所以节点定义要加两个标记位typedef struct ThreadNode { int val; struct ThreadNode *left, *right; int leftTag; // 0表示左孩子1表示前驱 int rightTag; // 0表示右孩子1表示后继 } ThreadNode;线索化的过程本质上是一次遍历在遍历过程中记录“上一个访问的节点”pre。当当前节点的左孩子为空时让左指针指向上一个访问的节点前驱当pre的右孩子为空时让它的右指针指向当前节点后继。这里的关键是“当前节点访问时看左”而“前驱节点看右”顺序容易搞混建议画图辅助记忆。中序线索化最常用因为中序的“左-根-右”顺序恰好让线索化后的遍历非常自然。前序和后序线索化也有应用但后序线索化的实现更绕实际用得少。6.3 遍历线索二叉树线索化之后遍历就没那么烧脑了。以中序为例void inorderThreaded(ThreadNode *root) { if (root NULL) return; while (root-leftTag 0) { root root-left; // 找到最左节点 } while (root ! NULL) { printf(%d , root-val); if (root-rightTag 1) { root root-right; // 直接走后继线索 } else { root root-right; // 有右孩子转去右子树找最左节点 while (root ! NULL root-leftTag 0) { root root-left; } } } }第一次看可能有点晕但你跟着一个简单的树走一遍就明白了第一步先一路向左找到中序第一个节点之后每个节点如果右标志是1直接跳后继不是1就转向右子树再一路向左找最左节点。这个“两步循环”就是线索二叉树遍历的全部秘密。如果你只是应付考试或面试线索二叉树一般考概念和理解手写完整线索化代码的情况不多。但你要是做嵌入式或者追求极致空间利用的工作这个思想值得好好掌握。7. 写在最后二叉树学习的几个实操建议7.1 画图是解决问题的第一工具我每次调试二叉树程序第一件事不是看代码是画图。拿一张纸或者用白板把树画出来把指针变化标出来。就是这么土的办法能解决我八成以上的困惑。特别是递归问题很多人的困境是“代码能跑但不知道为啥对”。这时候画一棵小树手动模拟递归的调用过程走两遍就通了。我至今保留着画树梳理递归的习惯强烈推荐你也试试。别高看自己的脑内模拟能力写下来更靠谱。7.2 做题和工程应用要分开在校刷题或者面试时递归版遍历完全够用代码短、逻辑清晰面试官也爱看。但到了工程项目里数据量一大递归栈溢出就是真事故了。所以我的建议是两种写法都要会并且要能说清楚各自的适用场景。你可以先写递归版本跑通逻辑再改成迭代版本验证结果这样就同时掌握了两套写法。7.3 把“空指针检查”焊死在脑子里说句掏心窝的二叉树程序出bug绝大多数不是算法不懂就是指针没管好。我在项目里见过太多因为漏掉一个NULL判断导致线上服务半夜崩掉的案例。不要觉得“这个节点肯定不为空”你要相信运行时的一切可能。写代码时无脑加上if (node ! NULL)这种守卫不会损失性能但能省掉大量调试时间。学二叉树就像学骑车理论讲再多不如自己骑两圈。把这篇文章里提到的代码都手敲一遍敲的时候思考一下root为NULL会发生什么再自己画几棵树模拟一下遍历过程。等你熟练了再看后续的AVL、红黑树、B树会觉得整个世界都顺了。希望这些内容对你有实际帮助也欢迎你在自己的项目里大胆用起来。