最近刷到二叉树part07的朋友，恭喜你，已经挺过二叉树最磨人的中序遍历、层序遍历和几道重建二叉树的硬骨头了。DAY20的第六章part07，主题非常集中，核心就是围绕二叉搜索树做文章：删除节点、插入节点、修剪区间、把有序数组还原成二叉搜索树，再加上最近公共祖先和累加树这几个经典操作。我自己在带训练营和平时给同学答疑时发现，这个阶段的题看起来都是“套模板”，但实际上手就各种懵，尤其是删除节点那题，分分钟被空指针和返回值的逻辑绕晕。
这篇就来聊聊DAY20二叉树part07的核心内容。我会尽量把训练营里那些“一句带过”的细节摊开讲清楚，包括为什么删除节点要分五种情况、递归返回值的本质是什么、修剪和删除到底哪里像哪里不像，以及我自己踩过的几个坑。无论你是0基础跟着训练营走的，还是二刷想加深理解的，这篇都可以当个参考。
1. 先看清这个阶段要打什么仗
1.1 从普通二叉树升级到二叉搜索树的钥匙在哪
前几次part刷的二叉树，比如翻转二叉树、对称二叉树、平衡二叉树，最大的特点是：我们操作的是节点的位置和结构，不关心节点值的大小关系。你就算把整棵树节点值乱换，只要结构不变，照样能跑那些题。但到了part07，题目几乎全部围绕“值的大小”展开，一切操作的第一驱动因素是：这是一棵二叉搜索树，左孩子一定比根小，右孩子一定比根大，严格一点说，左子树所有节点值小于根，右子树所有节点值大于根。
如果你不把这个性质刻在脑子里，后面的代码你写出来可能就是“能过样例但逻辑站不住”。比如插入节点，为什么代码非常简单，直接一路比较就到底了？不是因为题简单，而是因为BST的性质决定了新节点唯一的落点一定是一路比较下来的那个空位。再比如删除节点为什么比插入麻烦得多，因为删掉一个节点后，你得保证剩下的树依然满足“左小右大”的全局要求，而不仅仅是局部调整。
有些人觉得part07简单，其实是因为理解到了本质：中序遍历BST得到的是一个升序序列，这是整个part07无数解法背后真正的“第一性原理”。你把BST当成一个特化过的二分查找树来看，就明白了。所有的查找、插入、删除、修剪、转换优化复杂度，本质上都是在利用这个有序性做区间裁剪。
1.2 DAY20题单的整体脉络和底层共性
训练营里这一天的题单，我把它分成三条线：
第一条线是“节点的增删查改”。从搜索二叉搜索树的最近公共祖先，到插入节点，再到删除节点，这是一条很自然的操作线。公共祖先那题，如果放在普通二插树上，你得遍历全树、收集路径，复杂度高得多；但在BST里，利用值的大小区间，一次向下的搜索就搞定了。插入节点要靠递归的返回值把新节点“挂”回去，删除节点则是插入的进阶版，核心难点在于如何调整子树结构。
第二条线是“区间与重建”。修剪二叉树是在保住“节点值落在给定区间”的前提下调整结构，有序数组转二叉搜索树则是取中点作为根、分治建树。这条线的核心思想是“把有序集合按中点一分为二，递归构造左右子树”。
第三条线是“反向中序遍历”。把二叉搜索树转换成累加树，核心操作是中序遍历，但顺序是反着来的，先右后左，累加和过日子一般。这条线看起来独立，实际上还是在利用BST中序遍历的有序性，只是换了个遍历方向。
如果你能把这三条线串起来看，会发现part07大部分题目本质上是同一件事：利用BST有序性，通过递归在O(logn)或O(n)的时间复杂度内解决区间查询、节点操作或树的构建。理解的深度决定了你能否举一反三，不只是死记硬背代码。
2. 核心原理拆解：为什么代码要这么写
2.1 删除节点：这五种情况是状态机
删除二叉搜索树中的节点是part07最经典、也最劝退的一题。训练营讲得比较细，会把删除节点的逻辑拆成状态。老实说，我第一次写的时候也被绕晕过，后来发现：你如果理解了五种情况的判据，代码就只是照着情况分支而已。
我先说一下标准的五种情况：
- 没找到要删的节点：直接返回空（那递归返回的就是原来的树）。
- 找到了节点，且它左右孩子都为空（叶子节点）：直接删除，返回空。
- 找到了节点，只有左孩子，右孩子为空：让左孩子顶上来，删除当前节点，返回左孩子。
- 找到了节点，只有右孩子，左孩子为空：让右孩子顶上来，返回右孩子。
- 找到了节点，左右孩子都不为空：这是最复杂的情况。一种通用做法是，把当前节点的左子树整体挂到右子树的最左节点的左边，然后把右子树作为删除后返回的结果。另一种做法是，找到右子树的最小值（最左边节点），把根的值替换成这个最小值，再去右子树删除那个最小节点，然后把当前节点的右子树链接到递归删除的结果上。
很多新手卡在第五种情况，最大的困惑是：“为什么要把左子树接到右子树最左边节点的左边？”你只要想清楚BST的性质就明白了：右子树的所有节点都比根大，而右子树最左边的节点是右子树中最小的那个，但仍然比根的左子树所有节点都大。所以左子树挂到右子树最左节点的左下角，依然能保持左小右大的整体结构。这个操作就像把一个更小的子序列拼接到一个更大的升序序列的合适位置，保证整个序列依然升序。
我个人在训练营里讲解时，更推荐第二种做法：值替换法。逻辑上更符合直觉，代码写起来参数也简单。你只需要在右子树找到最小值，然后把根节点的值覆盖成最小值的值，再递归去右子树里删掉那个最小值节点。这样树结构变化最小，不需要大挪移，只要递归地在右半部分搜索删除即可。
# 删除二叉搜索树中的节点：使用替换值的思路 def deleteNode(self, root, key): if root is None: return None # 根据 key 和当前节点值的关系，决定去左子树还是右子树 if root.val > key: root.left = self.deleteNode(root.left, key) elif root.val < key: root.right = self.deleteNode(root.right, key) else: # 找到了要删除的节点 if not root.left and not root.right: return None elif not root.left: return root.right elif not root.right: return root.left else: # 找右子树的最左节点（右子树中的最小值） min_node = root.right while min_node.left: min_node = min_node.left # 用最小值覆盖当前节点 root.val = min_node.val # 去右子树中删除这个最小节点 root.right = self.deleteNode(root.right, root.val) return root return root有一个细节值得注意：在值替换法里，我调用的是self.deleteNode(root.right, root.val)，而不是直接找到min_node然后把它删掉。这是因为现在root.val等于那个最小值了，递归进入右子树再按值搜索一次，最终一定会再走进“要删除的节点”那个分支。看起来很绕，但好处是不用单独处理min_node的左右指针，递归帮你把结构维护好了。
2.2 递归返回值的真正意义：怎么把结果挂回父节点
很多同学在part06就学过递归的返回值用来干什么，但直到part07删除、插入、修剪这三道题，才发现自己根本没完全理解。你要是能想清楚“递归函数的返回值，在处理过程中到底起了什么作用”，那part07就已经拿下大半了。
拿插入操作来举例。新节点插入后，我递归调用root.left = self.insertIntoBST(root.left, val)。这里的返回值其实有两种理解：
- 第一种理解：返回的是“以当前下层节点为根的那棵子树，完成插入操作之后，新的根节点”。因为插入操作可能让这棵子树变得“更胖一点”，但树的根结构本身不会换，所以返回的还是原来的孩子节点。
- 第二种理解，更适用于删除操作：返回的是“以当前下层节点为根的那棵子树在删除过程中的结果”，这个结果可能是空、可能是原节点、也可能是新的子树根（比如右子树顶替的情况）。
所以你会发现，删除节点时代码里有好几个return直接返回新的根结构，比如return root.right。这就是因为：当前节点被删掉之后，它的父节点需要知道，原先挂在这里的子树变成了什么，因此整个子树的新根必须作为返回值向上传递。如果你在这一层不把新根返回给上层，那上层父节点的指针还是指向已经删除的旧节点，整条链就断了。
这个逻辑一定要搞懂，不然后面写修剪二叉搜索树时，也会出现“我怎么删了节点但树没变化”的诡异现象。其实不是树没变化，而是你没有把变化后的结果交还给父节点去更新指针。
我在给同学答疑时经常拿“办公室里换座位”来类比：每个父节点就像领导，只知道自己的下属是谁。下属们的内部结构如果要变化，底层干完活要逐级上报新的状态，领导才能更新通讯录。如果你底层换完了人，结果没跟顶层说，那顶层拿着旧的通讯录找过去，自然找不到人了。
2.3 修剪和删除的差异：剪的是“一整片”，不只是单个节点
修剪二叉搜索树这题是很多人的第二个坎。题目给你一个区间[low, high]，让你把BST中不在区间内的节点移除，但保留树结构，最后仍然是一棵BST。
有人看到“移除节点”就条件反射地套删除节点的逻辑，删来删去写了一堆复杂分支，结果还是错。其实修剪和删除最大的区别是：删除是精确删掉一个已知key值的节点，而修剪是只要节点值小于low或大于high，这个节点以及它的一部分子树，可能一整片都要被丢弃。
怎么理解“一片”？比如当前节点值比low还小。根据BST性质，当前节点的左子树所有节点肯定更小，全都注定要被剪掉，所以左子树根本不需要继续递归了；但当前节点的右子树里，可能有值落在区间的节点，也可能有部分小于low的节点，所以我们递归去修剪右子树，并把右子树修剪后的结果作为新的子树根返回。同理，如果当前节点值比high还大，那当前节点的右子树全部都可以剪掉，直接递归修剪左子树即可。
这就是修剪的代码为什么比删除还短的原因。你不需要像删除那样去处理“左右都不为空”的复杂结构调整，因为你只关心值区间在哪一侧越界了，越界的那一整侧子树直接放弃，留下的那侧递归处理，然后更新指针接回来。
# 修剪二叉搜索树 def trimBST(self, root, low, high): if root is None: return None # 当前节点值小于low，整棵左子树都不要了 if root.val < low: return self.trimBST(root.right, low, high) # 当前节点值大于high，整棵右子树都不要了 if root.val > high: return self.trimBST(root.left, low, high) # 当前节点在区间内，递归修剪左右子树 root.left = self.trimBST(root.left, low, high) root.right = self.trimBST(root.right, low, high) return root一个实用的调试技巧：遇到修剪这类题，如果你思考时不知道该剪掉哪些部分，不妨先把这棵BST做一次中序遍历，看看哪些值不在区间里，然后想象把它们“摘除”，剩下的部分需要怎么拼接。中序遍历后的序列会告诉你，删除的必然是序列开头的一段和结尾的一段，中间连续的部分保留下来。这样想，修剪的本质其实是“从有序序列里截取中间一段”。理解了这一点，再看代码就觉得非常顺。
2.4 有序数组转二叉搜索树：分治法的骨架
将有序数组转换为二叉搜索树，这题的核心是分治。给定升序数组，要构建一棵高度平衡的二叉搜索树，直观做法就是每次取数组的中间位置作为根节点，中间左边的部分构建左子树，中间右边的部分构建右子树。
为什么取中间就能保证“高度平衡”？因为每次把区间对半分，左右子树的节点数量最多差一个，递归下去，树的高度就能保持在O(logn)级别。如果这里你脑子一热，不取中间，比如直接取第一个元素当根，那你构造出来的就是一条链，整棵树就退化成一个链表，毫无平衡可言。题目要求的“高度平衡”正是通过这种分治结构来保证的。
代码实现比较简单，但你需要注意边界条件。如果数组为空，直接返回None；如果数组不为空，mid = len(nums) // 2向下取整，拿nums[mid]当根，左半边是nums[:mid]，右半边是nums[mid+1:]。递归去构建左右子树。
# 将有序数组转换为二叉搜索树 def sortedArrayToBST(self, nums): if not nums: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid + 1:]) return root这里有一个容易被忽略的性能细节：nums[:mid]和nums[mid+1:]每次都会复制数组切片，在数组很大的时候会有额外的空间和时间开销。在面试场景中，如果你希望表现更好，可以用双指针（左边界和右边界）来限制区间，避免切片。两种写法逻辑一样，但切片写起来舒服、出错少，比赛和训练营里用它问题不大。面试官追问优化的时候，你再改成双指针版本也不迟。
3. 实操过程与现场记录
3.1 递归写不出来的时候，先用例子手推一遍
我个人的习惯是，每道树题动笔之前，先在一张纸上画一棵具体的BST，然后推演一个具体的操作。比如删除节点，我就画一棵树：根是7，左孩子3，右孩子9，9下面左孩子8，右孩子10。然后试着删掉根7。这时候右子树的最左节点是8，于是把8复制到根的位置，再去右子树删掉原来的8。推演完这一步之后你会发现，递归调用中root.right = self.deleteNode(root.right, 8)会自动找到原来8的位置，因为8是右子树最左节点，沿着左指针一路下去就能找到，删除起来非常简单，因为它极大概率是叶子节点或只有右孩子。
手推的例子能避免你在代码层面空想。很多时候你代码写不对，不是因为语法问题，而是因为你压根没在自己脑子里把“树结构变化”跑通。训练营里学长学姐总强调“画图”，真不是废话。
我DAY20那天学的时候，花了40分钟死磕删除节点，越看代码越觉得像是背的。后来静下心把三种基本情况画了一遍，再把左右孩子都存在的复杂情况画了一遍，瞬间通了。从那之后，凡是涉及树结构调整的题，我一定会先在纸上画出操作前后两棵树，再对照写代码。
3.2 搜最近公共祖先：BST给了你一条捷径
二叉搜索树的最近公共祖先，可比普通二叉树的最近公共祖先好做太多了。普通二叉树你得自底向上回溯，或者用路径数组，代码不短。BST版的思路用的是值区间判断：给定节点p和q，它们的最近公共祖先一定满足“祖先节点的值位于p.val和q.val之间”。
为什么？因为BST的节点值左小右大。从根出发，如果当前节点值比p和q都大，说明p和q都在当前节点的左子树里，那么最近公共祖先一定在左子树，往左走；如果当前节点值比p和q都小，说明p和q都在右子树，往右走；直到找到第一个值处于p和q之间的节点，那它就是p和q的最近公共祖先。
这里有一个容易忽略的细节：p和q到底谁大谁小，对你写判断没有影响，你只需要同时和当前节点的值比较大小即可。我第一次写的时候习惯性假设p.val < q.val，结果代码里多写了一堆交换逻辑，其实完全没必要。
# 二叉搜索树的最近公共祖先 def lowestCommonAncestor(self, root, p, q): while root: if root.val > p.val and root.val > q.val: root = root.left elif root.val < p.val and root.val < q.val: root = root.right else: return root return None注意这里用的是迭代，比起递归，代码更简洁，空间复杂度从递归栈的O(logn)降到了O(1)。实际工程里能写迭代就尽量迭代，训练营代码模板偏爱递归是为了统一思维，但你要能自己写出迭代版本，面试是加分项。
3.3 累加树：反向中序遍历的魅力
把二叉搜索树转换为累加树这题，我第一次看到题面是有点懵的。什么叫“累加树”？简单说，就是把每个节点的值，改成原树中大于等于该节点值的所有节点值之和。因为BST的中序遍历是升序序列，所以“大于等于该节点值的所有节点”其实就是包括它自己在内的、排在它后面的那些节点之和。
那你想，如果按正常中序遍历，从左到右遍历，你根本不知道后面还有多少加起来是多少，除非你先遍历一遍求出后缀和。但如果你反过来，按右、根、左的顺序遍历，就能从大到小累计。每访问到一个节点，把累计值加上当前节点的值，然后把当前节点的值更新成这个累计值。这样整个树一遍遍历就完成，不需要额外数组。
# 把二叉搜索树转换为累加树 def convertBST(self, root): self.total = 0 def dfs(node): if node is None: return dfs(node.right) self.total += node.val node.val = self.total dfs(node.left) dfs(root) return root我在训练营里看到有人把self.total写成局部变量然后发现累加不生效，这个就是Python闭包作用域的经典坑。你在递归函数里直接赋值，会创建新的局部变量，不影响外层变量。所以要么用self.xxx，要么在函数内部声明nonlocal。这是个很隐蔽的小坑，错过了排查半小时起步。
3.4 众数问题：一棵树里的频率统计
除了训练营题单之外，二叉搜索树中的众数也是这个阶段非常典型的题目。它的特殊之处在于，BST的中序遍历序列是升序的，所以相同的值一定会连续出现。我们可以只用一个计数器，遍历过程中动态统计连续相同值的个数，同时维护当前的最大次数，从而得到众数，不需要借助HashMap记录所有节点值频次。
如果是一棵普通二叉树，你没法保证相同值连续出现，那就得老老实实遍历一遍存入哈希表再统计。但在BST上可以用这个巧妙的方式做到O(1)额外空间。这一题的代码也值得写一下。
def findMode(self, root): self.pre = None self.count = 0 self.max_count = 0 self.result = [] def dfs(node): if node is None: return dfs(node.left) if self.pre is None: self.count = 1 elif node.val == self.pre.val: self.count += 1 else: self.count = 1 if self.count == self.max_count: self.result.append(node.val) elif self.count > self.max_count: self.max_count = self.count self.result = [node.val] self.pre = node dfs(node.right) dfs(root) return self.result这个写法里有个细节：当新频率超过max_count时，结果列表需要重置。很多新手只记得self.result.append()，却忘了更新最大频率时要清空列表，导致答案里混入之前频率已经过时的节点值。
4. 常见问题与排查技巧
4.1 删除节点时空指针的坑
删除节点代码里最常见的报错就是AttributeError: 'NoneType' object has no attribute 'val'。出现这个问题的原因大多是递归调用时没有检查空节点，或者在找到最小节点时没有考虑右子树为空的情况。
我用一个习惯来规避这类问题：凡是涉及递归树操作的函数，第一行永远先写if root is None: return None（或者对应空值条件），把空节点的情况直接从源头拦住。第二，找右子树最小节点时，要考虑从root.right开始，沿着left一直走到头。如果root.right本身就是None，那说明当前节点没有右子树，属于前面几种简单情况，根本不会走进第五个分支。所以只要你分支判据写对了，这里不会出现空指针。
此外，值替换法里第二次递归删除时，传给递归函数的值是root.val，这时一定要清楚，这个值一定存在于右子树中，不会找不到。如果找不到，那就是你前面找最小节点的逻辑写错了，或者树本身不满足BST性质。
4.2 返回值的处理：到底什么时候return，什么时候改指针
这也是part07高频问点。很多人写出“能改但是没生效”的代码，回头一看，问题全出在返回值没接住。
具体来说，如果在递归里调用了root.left = self.deleteNode(root.left, key)，这个赋值是必须的。因为你删掉的可能是root.left本身或其子树里的某个节点，删除后的子树根可能会变化。如果你写self.deleteNode(root.left, key)，等于忽略了递归返回的新子树根，那上层指针永远指向旧节点，或者指向一个已经失效的节点。
但有一种情况你可以忽略返回值：如果你对某个节点的子指针本身没有修改需求，只是单纯访问或遍历，比如查找节点、遍历，那你当然可以不接收返回值。判定标准很简单：这次递归调用是否会改变目标子树的根？会变，就必须赋值接收；不会变，就不需要接收。插入节点会改变子树（挂上新节点）吗？严格说新节点总是挂在叶子空指针位置，子树根不变，但递归传递时还是需要把新建节点挂回去，所以依然要用返回值。删除节点会改变子树根吗？会。修剪会改变吗？会。公共祖先和累加树会修改节点值但不变根结构，所以返回值不是必须的。
4.3 修剪时越界的处理顺序
修剪二叉搜索树有个新手经常犯的错：先递归处理左右子树，再判断当前节点的值是否越界。这个顺序错了会导致大量无效递归。你想想，当前节点已经小于low了，它的左子树肯定全小于low，你还递归进去剪一遍干嘛？纯属浪费时间。
正确的顺序是先判断当前节点是否越界，再决定要不要递归子树。这其实就是“先裁大枝，再剪小枝”的思路，由顶向下做区间收敛。另外，有些同学在root.val < low时写了return root.right，漏掉了递归，以为右子树全都符合区间，这也不对。因为右子树的左子树节点可能仍然小于low。所以你必须递归修剪右子树后，再把它返回。
4.4 众数和累加树里的全局变量干扰
这两个题如果在一套代码里连续做，很容易出现全局变量残留的问题。比如你在测试用例里跑通了累加树，第二个测试用例又复用同一个对象，self.total没重置，导致结果完全错误。在刷题网站上这类问题不常见，因为每个测试用例通常重新创建对象，但如果是面试手写、或者你本地跑多个测试用例，就容易翻车。
个人建议在递归入口处重置这类状态变量，或者直接在函数内部定义辅助函数并初始化局部变量。比如：
def convertBST(self, root): total = 0 def dfs(node): nonlocal total if node is None: return dfs(node.right) total += node.val node.val = total dfs(node.left) dfs(root) return root这里用nonlocal声明外层变量，就能正常累计了。我个人更倾向于这种写法，因为状态局限于单次调用，不容易残留。
5. 复习路径与经验补充
5.1 从part07往后看：结构维护的通用思维
part07这些题做完，你会发现一个通用思维：对于BST的修改操作，要么用递归的返回值向上传递新子树，要么用值替换的方式避免复杂指针操作。这两种思路在未来写红黑树、AVL旋转的时候同样适用。你可以在复习时把插入、删除、修剪、数组转BST四题放在一起对比，画一张它们之间关系的图：插入是删除的逆向，删除的复杂之处在调整结构，修剪是区间化的删除，数组转BST则是在有序序列上分治建树。
我建议你别急着连续刷完DAY20的所有题，可以拆成两天。第一天专注删除和插入，把返回值机制吃透；第二天做修剪、数组转BST和累加树，把区间裁剪和中序遍历反向的思路消化掉。间隔一天会让你的大脑保留更深的印象。
5.2 二刷时可以做的“加餐”
如果part07对你来说已经比较轻松，可以自愿加餐几道延伸题，比如BST中查找众数、将BST展开为单链表、BST中第k小元素。它们和part07的题思路一脉相承：中序遍历有序性、分治递归、反向累积，练熟了对后续的BST更复杂操作非常有帮助。
当然，加餐不是必须的。训练营的进度已经很紧凑，能把这个part的每一道题独立写出来并且说清楚原理，就已经很了不起了。我更建议你把精力放在“讲题给自己听”上，每道题都能用清晰的步骤讲出来，比闷头多刷三道题更有用。因为讲题的过程其实在逼你整理思路，你往往会发现，看起来会做的题，讲出来的时候还是会卡住。卡住的地方，就是你的盲区。
最后分享一个小习惯。我在刷这类递归树题时，会特意在草稿纸上写出“函数进入某个节点时，我需要它完成什么任务，它可能的返回结果有哪些”。一旦你养成这个习惯，写出来的递归代码会非常稳定。二叉树part07真正难的从来不是语法，而是你对“递归在树中的流向”有多大掌控力。这只能靠画图、手推、反复练习来建立，什么捷径都没有。刷到这一步，你已经离二叉树这个章节的终点不远了，别停，继续往后推。
