代码随想录算法训练营的第六章二叉树我刷到了DAY21也就是part08。前面几天还在折腾遍历、深度、翻转、路径这些“看清一棵树”的基础操作到了今天这三道题风格一下子变了235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点全部围绕二叉搜索树BST展开。如果part01到part07教的是“怎么把树看清楚”那part08就是在教“怎么利用树的排列规则精准操作它”。这篇文章把当天刷题、看题解、调试代码的完整过程记下来既算自己的复盘也给正在跟训练营或者正在刷二叉树的朋友一个参考尤其适合那种“递归能看懂、自己写就卡壳”的选手。1. DAY21的转折点做题思路从“遍历”切换到“利用性质”1.1 为什么到了part08才集中出现BST代码随想录的二叉树章节不是按照LeetCode题号排的而是按照知识点层层递进的。DAY21之前的内容递归遍历、迭代遍历、层序遍历、翻转二叉树、对称二叉树、最大最小深度、路径总和、构造二叉树这些题有一个共同点题目给的二叉树是“普通二叉树”没有额外的排列约束。我们解题靠的是遍历整棵树把所有节点过一遍然后再在遍历过程中收集信息、做判断。但二叉搜索树不一样。它有一个非常强的前提对于任意一个节点它的左子树所有节点值都小于它右子树所有节点值都大于它。这个规则让很多操作从“必须看完整棵树”变成“只看一条路径就够了”。DAY21的三道题本质上是把BST这条性质用到了极致。可以说part08是整个二叉树章节从“遍历思维”转向“结构思维”的转折点。我一开始没意识到这个转变还是用前几天的老思路去解235结果写出来的代码又长又绕。后来看完Carl哥的题解才发现思路不换代码是不可能简洁的。1.2 BST三连题在DAY21的整体分工DAY21这三道题不是随便凑在一起的它们对应了BST最基本的三个操作查、增、删。235题二叉搜索树的最近公共祖先对应“查”。它利用了BST搜索路径的唯一性把原本在普通二叉树里需要自底向上回溯的问题简化成了一条向下的搜索路径。701题二叉搜索树中的插入操作对应“增”。它利用BST的插入位置唯一确定这一特性把插入变成了“查找失败时落位”的问题。450题删除二叉搜索树中的节点对应“删”。这是三兄弟里最难的一个因为删除会破坏结构需要重新调整树让它继续满足BST的性质。这三道题全部围绕“二叉树节点值的排列顺序”做文章。如果只是孤立地背每一道题的解法很快就会忘但如果你能看到它们背后都是“利用左小右大规则缩小搜索空间”那这一天的训练就真正到位了。2. 235. 二叉搜索树的最近公共祖先一条搜索路径直接给出答案2.1 普通二叉树的LCA做法在BST上显得很笨重在讲235之前必须先提一下236. 二叉树的最近公共祖先。普通二叉树找最近公共祖先标准解法是后序遍历递归去左子树和右子树里找p和q如果p和q分别出现在左右两侧当前节点就是答案如果只在一边找到就返回那一边的结果。这个做法很通用但它需要把整棵树遍历一遍而且在回溯过程中要一层一层往上传递“我这边找到了谁”的信息。BST完全不同。因为它左小右大所以给定p和q之后从根节点出发我们甚至不需要知道树长什么样就能判断下一步往左还是往右。举个例子p的值是3q的值是9当前节点值是7那么p一定在7的左子树q一定在7的右子树所以7就是我们要找的最近公共祖先根本不需要继续往下走了。这个判断在普通二叉树里是完全不成立的因为普通二叉树的节点分布没有规律。2.2 为什么“第一次落在[p, q]区间”就是答案这是235题最核心的一个思考点。BST的搜索路径是这样走的当前节点值同时大于p和q说明p、q都在当前节点的左子树里往左走当前节点值同时小于p和q说明p、q都在当前节点的右子树里往右走当前节点值夹在p和q之间包含等于的情况这个节点就是最近公共祖先。前两条比较好理解关键在第三条。为什么第一次遇到一个介于p、q之间的节点就一定是最近的公共祖先而不是更深层的某个节点可以用反证法来想。如果当前节点cur的值介于p和q之间说明p和q分别在cur的左右两侧子树里或者cur本身就是p或者q。那么cur的任何一个子节点都只可能包含p和q其中的一个不可能同时以它们为后代。既然最近的公共祖先必须是能同时“够到”p和q的那个节点那cur自然就是唯一选择。换句话说cur就是p和q在树中搜索路径的“分岔口”到了分岔口答案已经确定了。为了加深理解可以拿查词典做类比。普通二叉树找LCA像在一堆乱序的卡片里找两个名字共同出现在哪个分类下你得把所有卡片翻完才能确定。BST找LCA像在按字母排序的通讯录里查两个名字第一次翻到首字母介于两者之间的那个名字它一定就是两个名字所在分区交界的地方不可能更细了。2.3 递归和迭代两版代码以及我的选择235题的递归写法非常短TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root-val p-val root-val q-val) { return lowestCommonAncestor(root-left, p, q); } if (root-val p-val root-val q-val) { return lowestCommonAncestor(root-right, p, q); } return root; }因为题目保证p、q一定在树里所以递归到某一步一定会进入return root的分支不需要额外写终止条件。如果习惯更严谨的写法可以在函数入口加一个空指针判断但核心逻辑完全不受影响。迭代版本同样简单而且我个人更推荐在面试中优先写迭代版TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root) { if (root-val p-val root-val q-val) { root root-left; } else if (root-val p-val root-val q-val) { root root-right; } else { return root; } } return NULL; }我之所以推荐迭代版是因为BST的搜索路径本身就是一条直线while循环天然契合这种“一路往下走”的形态。相比递归迭代版不需要考虑函数调用栈也不容易在return的时机上犯错。我身边不少同学写递归版时容易犯一个错在“同时大于”分支里写成return lowestCommonAncestor(root-left, p, q);没错但有时候手一抖把left写成right或者漏掉return导致函数没有返回值编译报错后才反应过来。迭代版就没有这个问题逻辑更直白。2.4 一个小边界p和q是祖先关系还有一种情况需要留意p是q的祖先或者q是p的祖先。这时候搜索路径会碰到其中一个节点本身。按照代码的逻辑如果当前节点值等于p或q它会落入else分支直接返回当前节点。这符合题意对最近公共祖先的定义一个节点可以是它自己的祖先。很多人在讨论这道题时会忽略这个边界但实际测试用例一定会覆盖到。3. 701. 二叉搜索树中的插入操作返回值就是父子连接的关键3.1 插入的本质是“查找失败的位置”701题是三个题里代码最短的但它的思想价值一点也不低。题目要求在BST中插入一个值并返回插入后的根节点。刚看到这道题时我第一反应是插入节点需要先找到合适位置然后调整树结构可能会很复杂。但仔细一想BST的插入其实非常简单因为新插入的节点几乎总是作为一个叶子节点挂上去不需要改变任何已有节点的相对位置。为什么因为BST对每个节点的约束只有“左小右大”只要沿着根节点往下找走到某个空指针的位置把新节点放在那里树的其他部分完全不用动BST的性质依然成立。所以插入操作的本质就是一次“查找失败”的过程从根出发目标值比当前节点小就往左走比当前节点大就往右走直到遇到空指针这个空位置就是新节点的归宿。这个过程和查找一个不存在的值的路径完全一样。3.2 递归版让返回值充当父子连接的“接缝”Carl哥给的递归写法非常值得反复品味TreeNode* insertIntoBST(TreeNode* root, int val) { if (root NULL) { return new TreeNode(val); } if (root-val val) { root-left insertIntoBST(root-left, val); } if (root-val val) { root-right insertIntoBST(root-right, val); } return root; }这段代码最妙的地方在于递归函数返回值是“插入完成后这棵子树的根节点”。当root为空时新建节点返回当val比root小时去左子树插入并用返回值覆盖root-leftval比root大时同理。通过这个设计新节点和原有树的连接完全不需要在调用方额外处理递归函数自己就把父子关系搭建好了。我第一版写这道题时脑子里还是“在函数里操作指针”的思路试图用一个全局变量保存新节点再手动把它接到父节点上结果代码写得很乱。后来才意识到二叉树的递归操作尤其是涉及结构改变的最容易的写法就是让递归函数返回“这一层处理完之后的节点”然后在上一层用赋值语句接住。这种“返回值接缝”模式在450题里会发挥更大的作用。3.3 迭代版parent指针是核心迭代版要自己维护一个parent指针否则当cur走到NULL时我们不知道新节点该挂在哪个父节点下面。代码是这样TreeNode* insertIntoBST(TreeNode* root, int val) { if (root NULL) { return new TreeNode(val); } TreeNode* cur root; TreeNode* parent NULL; while (cur) { parent cur; if (cur-val val) { cur cur-left; } else { cur cur-right; } } TreeNode* node new TreeNode(val); if (parent-val val) { parent-left node; } else { parent-right node; } return root; }写迭代版最常见的坑是while循环里cur移动之后忘了更新parent或者把parent的更新放在赋值之后导致parent始终落后两步。我的经验是在循环体开头第一行先写parent cur;再移动cur这样不容易出错。另一个容易忽略的点是返回的是原来的root不是新插入的node。因为插入没有改变根节点的位置题目要求返回插入后整棵树的根直接return root即可。如果root本身就是空树就单独处理返回新建节点。3.4 为什么很多人会觉得这道题“太简单”我在训练营群里看到不少人说701题比前一天的构造二叉树简单太多。确实从代码量上看701题就是一个简化版的查找。但我觉得这道题的简单是建立在“递归返回值接缝”这个思想之上的。如果你只是背下了代码却没理解root-left insertIntoBST(root-left, val)这句赋值到底在干什么那到450题删除节点时就会原形毕露。所以我在DAY21的笔记里专门把这句赋值标了重点它是接下来所有二叉树结构调整题的通用骨架。4. 450. 删除二叉搜索树中的节点五种情况难点全在“左右都不空”4.1 删除为什么比插入复杂一个量级701题插入新节点挂在叶子位置原有结构零改动。450题删除就完全不一样了删掉一个节点之后如果它还有孩子就得想办法把这些孩子重新安置好并且让整棵树继续满足BST规则。这个“重新安置”的过程是很多人的心理阴影。Carl哥把删除节点的情况分成了五大类我一开始记不住后来发现完全可以自己推导出来。推导的起点就是删除一个节点需要让父节点重新指向一个合适的子树。这个合适的子树可能是NULL可能是原节点的左子树可能是原节点的右子树也可能是经过重新组装的两棵子树。4.2 五种子情况的完整推导和代码先把删除节点时当前节点的值等于key的处理逻辑按情况拆开情况描述处理方式情况1叶子节点直接返回NULL父节点指针指向空情况2左子树为空右子树不为空返回右子树根节点情况3右子树为空左子树不为空返回左子树根节点情况4左右子树都不为空把左子树嫁接到右子树的最左节点下返回右子树根节点递归代码对应如下TreeNode* deleteNode(TreeNode* root, int key) { if (root NULL) { return NULL; } if (root-val key) { // 情况1叶子节点 if (root-left NULL root-right NULL) { delete root; return NULL; } // 情况2左空右不空 else if (root-left NULL) { TreeNode* ret root-right; delete root; return ret; } // 情况3右空左不空 else if (root-right NULL) { TreeNode* ret root-left; delete root; return ret; } // 情况4左右都不空 else { TreeNode* cur root-right; while (cur-left ! NULL) { cur cur-left; } cur-left root-left; TreeNode* ret root-right; delete root; return ret; } } if (root-val key) { root-left deleteNode(root-left, key); } if (root-val key) { root-right deleteNode(root-right, key); } return root; }情况1到情况3其实可以合并因为情况1是情况2和情况3的特例子树都为空时返回NULL和返回任意空子树结果是一样的。但分开写更容易和Carl哥的讲解对应也方便在面试时向面试官展示思路的完整度。4.3 情况4为什么要“把左子树接到右子树最左节点的左边”这是整道题最需要理解的地方。假设要删除的节点是targettarget有左右两棵子树。首先明确一个基本事实target的左子树中所有节点的值都小于target的值target的右子树中所有节点的值都大于target的值。删除target之后我们想保留这两棵子树就必须把它们拼成一棵满足BST性质的树。拼法不止一种Carl哥给的方案是找到右子树中的最左节点这个节点是右子树里值最小的节点它的左指针一定是空的因为它已经是“最左”了。把target的左子树整体挂到这个节点的左侧然后让target的右子树顶替target原来的位置。这样拼完之后BST性质是否依然成立关键看两点第一右子树最左节点的左子树也就是挂过来的target左子树里所有值一定小于右子树中任意节点的值。因为target左子树所有节点值都小于target而target又小于右子树所有节点所以传递下来target左子树所有节点值都小于右子树所有节点值。把target左子树挂在右子树最左节点的左侧不会破坏右子树内部的顺序。第二右子树内部其他节点关系没有被改动仍然是BST。所以整个操作本质上就是把左子树整体降级为右子树最左节点的左孩子右子树晋升为新根。同样地也可以对称地用“把右子树挂到左子树最右节点的右边”但Carl哥的版本在代码实现上更直接遍历到最左节点的过程也不需要额外的递归操作所以我最后采用的是这个方案。4.4 替代方案用右子树最小节点替换被删节点还有一种常见的面试写法是在左右子树都不为空时找到右子树的最小值节点把它赋值给当前节点然后递归去右子树删除那个最小值节点。核心代码如下if (root-left root-right) { TreeNode* minNode root-right; while (minNode-left) { minNode minNode-left; } root-val minNode-val; root-right deleteNode(root-right, minNode-val); }这个方案的好处是树的结构调整更小坏处是要多一层递归而且把“删除”变成了“先覆盖值再删更简单的节点”。两种方案都能过题。我建议训练营阶段先把Carl哥的方案吃透因为它不涉及递归删除节点的嵌套逻辑更直白等刷到后面平衡树部分再回头对比两种方案理解会更立体。5. 三道题背后的统一范式让递归返回值充当子树的“接缝”5.1 从235到450同一个结构反复出现DAY21这三道题表面上是三个不同的操作但如果你把代码放在一起对比会发现它们的骨架非常像235题返回值是“最终答案节点”递归函数在找到目标时直接return。701题返回值是“插入后的子树根”上一层用root-left ...或root-right ...接住。450题返回值是“删除后的子树根”上一层同样用赋值接住。701和450的共同点尤其明显它们都在递归过程中修改树结构修改的结果通过返回值传回上一层然后用一句简单的赋值把新子树接到父节点上。我把它叫做“返回值接缝模式”——递归调用就是一道接缝上一层的节点指针通过赋值语句和下一层的处理结果重新焊接在一起。5.2 为什么用“返回子树根”而不是“直接操作指针”有的朋友可能会想既然C里有指针为什么不直接在递归里修改节点指针非要返回一个节点举个例子删除一个节点后父节点原来的left指针应该指向什么如果你不告诉父节点父节点是不知道的。递归函数返回子树根就是把这个信息显式地传递出去。假设一个场景root-left这棵子树经过删除之后根节点换了。如果递归函数只负责在子树内部操作不返回新根那root-left还是指向旧的内存地址整棵树就断了。反过来如果用返回值覆盖root-left父节点就永远知道自己的孩子是谁。这个思想在链表题里也很常见比如删除链表节点时经常需要prev-next deleteNode(prev-next, val);本质是一样的。5.3 这个范式对后面AVL树、红黑树学习的意义DAY21之后代码随想录的二叉树部分还会继续深入之后如果去了解AVL树、红黑树旋转操作同样是这个模式。比如AVL树的左旋root-right root-right-left; // 调整指向后再返回新根旋转函数同样返回“旋转后的子树根”父节点用赋值接住。如果你在DAY21就建立了“递归返回值是子树接缝”这个认知后面看平衡树的调整会顺畅很多。如果这一步没有打通后面看到左旋右旋的代码时很容易被那一堆指针赋值绕晕。5.4 什么时候可以不使用这个范式也要说清楚不是所有二叉树递归题都需要返回节点。比如前面做过的翻转二叉树可以直接在函数内部交换左右孩子不需要返回值因为节点的身份没有改变只是孩子互换了。但凡是涉及“某一个子树被替换成另一棵子树”或者“子树根发生变化”的操作返回值接缝模式就是最自然的选择。判断标准很简单如果这一步会让父节点指向新的内存地址就必须让父节点通过赋值获得这个新地址也就是必须用返回值。6. 实战复盘训练营里最容易踩的三个坑和自查清单6.1 我在写450时真正踩过的坑第一天写450题我犯了一个特别低级的错误在情况4里找到右子树最左节点之后我直接把cur-left root-left写成了cur root-left。编译器不报错但运行结果完全不对整棵树直接乱套了。这个错误浪费了我将近二十分钟。后来再看Carl哥的代码才发现一个很关键的细节cur是用来“定位”的cur-left才是用来“修改”的。定位和修改不是一回事这种错误在二叉树的调整类题目里特别容易犯。另一个坑出现在递归调用的接缝上。删完节点后如果当前节点的值不等于key我是需要继续递归左子树或右子树的这时候必须写root-left deleteNode(root-left, key);而不是只写deleteNode(root-left, key);。后者等于白删因为返回值没有接住父节点仍然指向旧的、已经被释放的节点接下来遍历时会访问非法内存。这种错误在LeetCode上不一定立刻崩但本地跑或者反复提交时可能产生随机错误非常隐蔽。6.2 针对三道题的自查测试用例清单训练营的做法是每道题提交通过后再自己构造几个测试用例验证。对于DAY21这三道题我常用下面这组用例来检查代码题目测试用例期望验证点235树为单链表结构p是根q在右子树深处p本身是祖先的情况235p和q分别在根的两侧子树答案是根节点701空树插入返回新节点本身701目标值比所有节点小插到最左根节点不变450删除叶子节点父节点对应指针自动置空450删除只有左子树的节点左子树顶替上来450删除左右子树的节点左子树被接在右子树最左节点左侧450删除不存在的值树结构完全不变这些用例不用全跑但在本地调试时把树的前序遍历结果打印出来对比一下基本就能确认改动是否符合预期。特别是450题前序遍历能明显看出嫁接后树的形状。6.3 DAY21的刷题节奏建议我个人的经验是三道题不要一口气全看完题解再写那样容易产生“我全懂了”的错觉。先把235做掉做完后停下来总结一下BST搜索路径的特点再开始701做完后重点感受递归返回值的接缝用法最后啃450。如果卡在450超过四十分钟直接看Carl哥的视频不要硬扛。硬扛两小时效率太低而且容易打击信心。还有一个训练营内部流传的经验睡前把当天三道题的代码各自默写一遍。默写不是背代码而是默写完了之后能在每一行旁边写出一句注释解释这行代码在干嘛。写不出来的地方第二天早上立刻重新打开题解再看。我到现在还记得第一遍默写450时情况4的嫁接逻辑还是有点磕巴但第二遍就非常流畅了。这种肌肉记忆对面试手撕代码帮助极大。6.4 回到DAY21整体收获现在回头看DAY21我最深的体会是二叉树的题目越往后越不考“你会不会递归”而是考“你能不能理清节点的身份变化”。插入和删除之所以比遍历难是因为它们要回答一个具体问题改动之后这个位置应该放哪一个节点答案就藏在递归函数的返回值里。搞懂这一点part08就算真正通关了。