★ FEATURED ARTICLE 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*i1。这种方式的槽点很明显如果是一棵“斜树”也就是每层都只有一个孩子比如一直往左长那数组得开得非常大中间会有大量空位。但如果是完全二叉树或满二叉树顺序存储就非常香因为下标能直接算出父子关系连指针都不需要内存连续缓存命中率还高。我个人的建议是初学阶段把链式存储吃透因为面试笔试几乎都是链式等理解了二叉树的本质之后再去感受顺序存储你会发现用数组写堆排序的时候特别顺手其实堆就是一棵顺序存储的完全二叉树。数据结构这东西存储方式服务于操作需求没有绝对的好坏只有适不适合。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个剩下n1个空指针全部浪费。线索二叉树把这些空指针利用起来分别指向遍历序列中的前驱和后继节点这样遍历的时候不需要递归或栈直接顺着线索走即可。这是个很细的考点面试出现的频率不算最高但一旦问到就是考察你“是否真正理解指针的意义”。4.1 搜索二叉树的查找与插入一次行走的递归BST的查找和数组二分查找本质是一回事只不过载体从数组变成了树。从根出发目标值比当前节点小就往左走比当前节点大就往右走相等就命中。整个过程就是一条从根到某个节点的路径最坏情况是走到叶子还没有树高就是最大比较次数。插入的逻辑和查找几乎一致也是从根出发找到合适的位置挂上。区别在于插入前需要判断如果当前节点为空说明找到了插入点直接新建节点返回否则按大小比较决定往左递归还是往右递归然后把递归的返回值挂到当前的左或右指针上。这里有一个非常容易写错的地方递归函数要返回更新后的子树根否则你新建的节点挂不上树。很多新手写成“递归进去不接收返回值”结果树还是原来的树怎么插都插不进去。记住经验法则凡是修改树结构的递归基本都要带着返回值return newRoot并把返回值赋值给父节点的对应指针。BST的删除是三兄弟里最麻烦的核心难点在于删除的节点可能有两个孩子。经典策略是找到右子树中最小的节点来顶替被删节点的位置或者用左子树最大的节点。这样能保证替换后仍然满足BST的定义。具体实现上找右子树最小节点就是一个“一直往左走”的过程再把那个节点的值赋给当前节点然后递归删除右子树里的那个最小节点。这段逻辑看起来绕但思路扎实强烈建议在纸上画几个例子再写代码。4.2 线索二叉树把空指针变成“高速公路”先说思路。线索二叉树要利用空指针如果某个节点没有左孩子就让它左指针指向“中序遍历时它的前驱节点”如果没右孩子就让它右指针指向“中序遍历时它的后继节点”。为了区分这个指针到底是原本的孩子指针还是线索每个节点还得加两个布尔位比如ltag和rtag0表示正常孩子1表示线索。线索化的过程本质上是在中序遍历的过程中完成的用一个全局指针pre记录“上一个访问的节点”。当遍历到当前节点时若它的左孩子为空就把左指针指向pre并设置ltag1若pre非空且它的右孩子为空就把pre的右指针指向当前节点设置rtag1然后更新pre为当前节点。这个“现场接线”的步骤非常考察你对遍历过程的理解因为线索的顺序完全由遍历顺序决定。为什么线索二叉树有实用价值因为普通二叉树中序遍历必须先递归到最左子树再一层层回来这个过程需要栈而线索化之后你可以从第一个节点开始通过右线索一路定位后继直到结束不需要任何栈和递归。这在“频繁需要遍历”的场景下节省的时间和空间都很可观。不过线索二叉树也有代价插入、删除节点时要维护线索逻辑复杂度明显上升所以工程上用得不多更多出现在教材和考试里。4.3 二叉树的应用场景从超市货架到文件系统很多人学数据结构会问“这玩意儿到底有啥用”我特别喜欢用一个“超市货架”的例子来回答。假设超市里有数不清的商品每个商品有货号。如果你用一个无序链表维护商品信息找一个商品要遍历全表顾客结账会慢到崩溃。但如果用BST存货号每次查询可以砍半搜索数据量大时差距立竿见影。这个例子对应热词里那个有趣的组合“超市货架 遍历二叉树”——货架的物理排列可以看作一层层节点而管理系统的索引结构底层就是一棵二叉搜索树。你用层序遍历的思想去巡检货架从入口到最里排先访问当前排再处理左右通道这和遍历二叉树的逻辑一模一样。再往深了说操作系统的文件目录就是一棵树编译器的表达式解析会把“ab*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 常见问题排查速查表为了方便你对照自查我把二叉树程序最常见的运行时错误整理成了一张表基本涵盖初学者遇到的所有典型情况。错误现象常见原因排查步骤程序启动即崩溃报Segmentation fault访问了空指针如node-left时node为NULL检查函数入口是否统一判空检查递归出口是否覆盖空节点程序运行后无输出疑似卡死递归缺少出口或递归参数没变化导致无限递归用日志打印递归进入次数检查出口条件是否真的能被终止插入节点后树没变化递归返回值没接住新建节点丢失确保所有修改结构的递归都以node-left insert(...)形式返回并赋值输出顺序不对先序、中序、后序的代码顺序搞混对照“根左右/左根右/左右根”逐行检查打印位置大数据量下栈溢出树过深或递归栈消耗过大改用显式栈迭代确认递归深度是否超过系统栈限制部分节点访问不到遍历出口误判为“叶子才返回”导致空左子树被跳过统一使用if(node NULL) return;作为递归出口层序输出只有一层忘记用一个变量保存当前层节点数导致每层混在一起在循环开头取队列当前长度仅弹出该长度的节点数这张表的左侧是现象右侧是排查方向。实际遇到问题的时候先想清楚“它是指针问题还是递归问题”再去翻对应代码效率会高很多。很多人在二叉树程序上耗时太久不是代码能力不足而是排查方式太随机没有体系。有了这个表你至少能少走一半的弯路。6. 最后再分享几个写二叉树代码的个人习惯写到最后我想聊几个我自己的个人习惯。这些东西不算什么高深理论纯粹是踩过坑之后养成的肌肉记忆但确实让我的二叉树代码比以前稳很多。第一个习惯是任何涉及指针操作的地方先问“这个指针可能为空吗”。不管是入口参数、左孩子、右孩子还是递归调用的返回结果只要有一丝可能为空就统一处理。写代码的时候可以多写几个防空的if写完再回头看看有没有冗余这是“先求对再求美”的思路比一次性追求简洁要可靠得多。特别是C语言这种没有自动垃圾回收和空指针安全的语言判空永远不过分。第二个习惯是结构体里总是额外带一个计数器或者层次字段。比如我在调试二叉树的深度时经常临时给节点结构体加一个int depth字段在插入时维护深度信息这样查起来就少很多递归调用的麻烦。虽然正式代码里不一定要带但调试阶段这些“冗余字段”能救命。等程序稳定了再决定哪些字段该留下哪些该删掉。第三个习惯更实用凡是写递归我都先在注释里写清楚“当前节点要做什么、左子树返回什么、右子树返回什么”。先写注释再写代码比先写代码再补注释出错率低得多。尤其是那些返回值类型是“子树根”的递归如果没有事先想清楚返回语义很容易写出一半截逻辑。另外我想特别说一句关于学习路径的话。如果你正在自学二叉树别指望看一遍教程就能打通所有题目。我当年是每天挑几道LeetCode上的简单题反复刷从求深度、求节点数、层序遍历、翻转二叉树这四道题开始刷到滚瓜烂熟后面很多题自然就通了。二叉树这个知识点的特点是它太依赖“手感”只看不做永远隔着一层纱。你亲手写过一遍层序遍历的队列实现再遇到“按层分组输出”就不会发怵你被段错误折磨过一次以后写任何树的代码都会条件反射先判空。如果还要再给一条建议的话那就是学着在纸上画递归展开的过程。遇到复杂的题目比如“最近公共祖先”“路径总和”不要急着在电脑前硬调先在草稿纸上把一棵三层的二叉树画出来逐步模拟每个节点在递归过程里经历了什么。这个习惯能帮你真正建立递归的直觉而且对面试时的沟通表达也有很大帮助。二叉树的精巧之处就在于它用朴素的结构托起了一整个计算机科学的世界值得你静下心来慢慢消化。
阅读完成 · 觉得有帮助？
参数详解与数据清洗实战指南)
