二叉搜索树进阶四连击：删除、修剪、构造与累加树的递归精讲

我们这个系列的二叉树刷题已经走到了第十五期。能坚持到这一步的读者，大概率已经刷过了前序遍历、中序遍历、后序遍历、层序遍历、翻转、对称、路径总和这些基础关口。但二叉树的知识远不止这些，真正在面试里拉开差距的，往往是从二叉搜索树这一族题目开始的。

这一期的题目组合很特别：删除二叉搜索树中的节点、修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转成累加树。四道题，四个完全不同的操作场景，却共用同一套递归能力。你只要把这四道题吃透，二叉树部分百分之八十的变形题都不会再慌。

这篇文章适合两类读者：一类是刷完二叉树基础题、准备系统强化二叉搜索树的同学；另一类是已经写过不少题、但遇到“删除节点后要返回新树根”这类问题时还会卡壳的开发者。我会尽量把每一步的“为什么”讲清楚，因为这类题目最怕的不是代码写不对，而是写完不知道自己为什么对。

开头先给一个我个人判断：如果你能独立写清楚“删除二叉搜索树节点”这一题，并讲明白递归返回值什么时候必须接住、什么时候可以忽略，那你对二叉树递归的理解就已经超过了绝大多数候选人。为什么这一题这么关键？往下看你就会明白。

1. 第十五期的选题思路：为什么把四种经典变式放在一起

1.1 这一期刷什么：删除、修剪、构树、累加

先把这四道题摆在一起，做一个全景对比：

单纯看题目描述，好像每一道都在考不同的事情：删除考的是指针调整，修剪考的是区间判断，构造考的是分治，累加考的是遍历顺序。但你把它们放在一起做一遍就会发现，所有题目都围绕着一个核心问题——递归到底要返回什么。

删除和修剪返回新树的根节点，构造题用递归返回每棵子树的新根，累加树虽然不改变树的结构，但递归时也要考虑当前累加值的传递方式。只要能把“递归返回值”这条主线想明白，这四道题就是一套连贯练习，而不是四道孤立的题。

1.2 一个核心能力：递归该返回什么

很多人刷二叉树题的时候有个误区：总想记住某道题的答案。其实二叉树的题目数量再多，底层能力就三样——递归的终止条件是什么、单层递归要做什么、递归返回值怎么处理。

第15期这套题目，最大的训练价值就是“返回值处理”这件事。

先说最简单的例子。层序遍历、路径总和这类题，递归通常不需要有意义的返回值，函数定义成void都没问题，参数里带一个路径状态数组就够了。但一旦涉及“增删节点后返回新根”，返回值就变成必须认真设计的东西了。

删除BST节点需要返回新树的根节点。原因很直接：当前这一层递归把目标节点删除后，这棵子树最高的那个节点可能已经不是原来的节点了，上一层必须收到这个新的根，才能正确链接到自己的左子树或右子树上。

有序数组转BST也一样。每次递归从区间中间取一个值建节点，这个节点要拼接到父节点的左或右孩子位置，靠的就是返回创建出来的节点指针。

所以这一期刷完之后，你应该形成一种条件反射：看到“树的形态发生变化”的题目，先问自己一句，递归函数要不要返回新的根节点？这一步想清楚了，后面写代码就是顺水推舟的事。

2. 删除二叉搜索树节点：最容易被细节击穿的一道题

2.1 五种情况的递归写法

删除BST节点的题，LeetCode原题编号是450，面试热度相当高。题目描述不复杂：给定一个二叉搜索树的根节点 root 和一个值 key，删除该树中值等于 key 的节点，并保证删除后仍然是一棵二叉搜索树，返回新树的根节点。

这道题最容易在“节点既有左子树又有右子树”的分支上翻车。我先把完整可跑的递归版本写出来：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) { return nullptr; } if (root->val == key) { // 情况1：叶子节点，直接删 if (root->left == nullptr && root->right == nullptr) { delete root; return nullptr; } // 情况2：右孩子为空，左孩子补位 else if (root->right == nullptr) { TreeNode* leftChild = root->left; delete root; return leftChild; } // 情况3：左孩子为空，右孩子补位 else if (root->left == nullptr) { TreeNode* rightChild = root->right; delete root; return rightChild; } // 情况4：左右孩子都在，把左子树挂到右子树的最左节点下 else { TreeNode* cur = root->right; while (cur->left != nullptr) { cur = cur->left; } cur->left = root->left; TreeNode* newRoot = root->right; delete root; return newRoot; } } if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } return root; }

这个写法的核心思路是：先利用BST的有序性，把搜索目标节点的过程变成一个走迷宫的过程——比当前节点小就往左走，比当前节点大就往右走，相等就停下处理删除。

很多人写这题的时候容易把“找到目标节点后的处理”和“没找到继续往下走”混在一起，代码写成分叉的if (root->val > key)和if (root->val < key)，结果忘记处理相等的情况。我的建议是：先写if (root->val == key)整块处理，再写往左往右递归，逻辑更清晰。

2.2 为什么不能偷懒返回右孩子

情况4是树上最难理解的地方：左右孩子都在时，为什么不能直接把右孩子返回，把左孩子丢掉？

我先说结论：如果直接返回右孩子，左子树里所有节点就凭空消失了，这肯定不符合BST的定义。那能不能把左孩子挂到右孩子下面任意位置？也不行，BST是有序的，挂错位置会破坏大小关系。

正确的做法是，把左子树挂到右子树“最左下角”那个节点下面。为什么是最左下角？

右子树最左下角的节点，是右子树里值最小的节点。而根据BST的性质，左子树里所有节点的值，都严格小于目标节点的值；右子树最左下角节点的值虽然也是右子树里最小的，但它仍然大于左子树里的所有节点。因此左子树挂在这个节点下面，依然能保持左小右大的整体结构。

用一句话记忆就是：左子树整体都比右子树最小值小，所以挂到右子树最左下角最安全。

还有一种等价的写法，就是找到右子树最左下角的节点后，不移动左子树，而是把那个节点的值赋给当前根节点，然后递归去删除那个最左下角节点。这种写法的好处是不用频繁改指针，但要注意递归深度可能会增加一层，边界上不如第一种直观。

2.3 迭代版怎么处理

面试的时候如果你已经写了递归版，面试官再追一句“那你用迭代写一遍”，不少人是会卡住的。删除节点的迭代版，关键点在于：递归版利用调用栈记住了父节点，迭代版必须自己记录父节点。

迭代版的思路可以拆成两步：

1. 先用一个指针cur从根出发，按BST搜索规则找到值等于 key 的节点，同时用parent记录它的父节点。
2. 删除节点后，要把新的子树根（可能是被删节点的左孩子、右孩子，或者经过调整后的右孩子）接回parent的对应位置。

这里有一个容易踩的坑：如果cur本身就是根节点，没有父节点，删除后要更新整个树的根节点。所以迭代版代码通常会单独设置一个虚拟头节点指向根节点，这样删除根节点的逻辑就不用单列了，统一走parent指针更新。

我实际写下来，迭代版的代码量大约是递归版的一倍，而且很容易在指针连接处出错。平时练习可以两个版本都写一遍，面试的时候优先选自己最有把握的版本，不必硬逼自己当场写迭代版。

3. 修剪二叉搜索树：把“区间”变成代码条件

3.1 前序遍历的递归思路

删除BST节点是按给定的一个值精确删除，但很多时候题目要求的是“删除所有值不在某个区间里的节点”。LeetCode 669 就是这样一道题：给你BST的根节点和区间 [low, high]，修剪这棵树，使所有节点的值都在区间内。

这道题我在代码随想录的二叉树篇里刷的时候，第一反应是“那就逐个删除每个不在区间内的节点”。这个思路能通，但很笨。更高效、也更符合递归美感的做法，是直接利用BST的结构特性做整体剪枝。

递归的思路其实就三条：

• 如果当前根节点的值小于 low，说明当前节点和它的整棵左子树都小于 low，全部丢弃，直接返回修剪后的右子树。
• 如果当前根节点的值大于 high，说明当前节点和它的整棵右子树都大于 high，全部丢弃，直接返回修剪后的左子树。
• 如果当前节点在区间内，那就保留当前节点，递归修剪左子树和右子树，再把修剪结果接回root->left和root->right。

对应代码如下：

TreeNode* trimBST(TreeNode* root, int low, int high) { if (root == nullptr) { return nullptr; } if (root->val < low) { // 当前节点和左子树都可以扔掉 return trimBST(root->right, low, high); } if (root->val > high) { // 当前节点和右子树都可以扔掉 return trimBST(root->left, low, high); } // 当前节点在区间内，处理左右子树 root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; }

这段代码练的是“递归返回新根”的习惯：当根节点越界时，直接把这个根节点丢掉，返回修剪后的子树；当根节点在区间内时，单独修剪左右子树再把结果赋回。

3.2 和删除节点对比后我总结的规律

做完修剪BST这题，再回头看上一节的删除BST节点，你可能会发现一个很有意思的对比：它们都在改树的结构，但改法很不一样。

删除BST节点时，需要搜索目标节点，搜索路径上的节点值都和目标值有大小关系。找到目标节点之后还要处理复杂的五情况。而修剪BST时，我们根本没有刻意去搜索某个节点，而是在前序遍历中，用当前节点值是否越界来判断该舍弃哪一侧子树。

我总结成一个比较容易记住的表述：

删除是“找到目标再处理”，修剪是“越界就整体剪掉”。

删除某个节点，如果左右孩子都在，需要把左子树挂到右子树最左下角。修剪则不需要这个操作，因为当根节点小于 low 时，它的右子树可能有一部分在区间内，直接对右子树递归修剪就行，天然避开了“复杂的五情况”。

另外一个区分点是递归顺序。删除节点是典型的“搜索式递归”，每一层只走左或只走右，整体复杂度是O(log n)。修剪树是“全套递归”，每个节点都要访问一遍，整体复杂度是O(n)。这两个复杂度差异要在脑子里记清楚，答复杂度问题的时候经常被问到。

3.3 边界写法实测

修剪树这题的边界条件特别值得单独看一眼。区间边界相等的场景，比如 low = high，最终得到的树最多只有一个节点，而且这个节点的值必须等于 low。

代码里的判断条件用的是root->val < low和root->val > high，等于号的情况全部落进“当前节点在区间内”的分支，这样能保证边界值不会被误删。

我测试过几组用例，给你参考：

• 空树：[]，任意区间，输出空。
• 单节点树，值正好等于 low：保留。
• 单节点树，值小于 low：丢到只剩空树。
• 有序序列构建的BST，区间只包含中间若干个值：整棵子树会做组合重组，代码会递归剥掉外围所有越界节点。

边界条件还有一个比较容易忽视的细节：如果题目给你的不是BST，而是一棵普通二叉树，同一套代码是不能直接用的。因为普通二叉树没有左小右大的性质，越界节点的左子树里也可能存在合法值，不能一起剪掉。做题之前一定要看清题目说的是BST还是普通二叉树。

4. 有序数组构造平衡树、BST转累加树：两道面试高频变形题

4.1 有序数组转平衡BST的分治与迭代

LeetCode 108 的原题是：给定一个升序排列的整数数组，把它转换成一棵高度平衡的二叉搜索树。所谓高度平衡，指的是任意节点的左右子树高度差不超过 1。

数组有序这个条件非常重要。BST的中序遍历结果本身就是一个递增序列，所以要把升序数组还原成一棵BST，最自然的思路就是分治：每次取区间的中间元素作为当前子树的根，左半区间递归构造左子树，右半区间递归构造右子树。

我写的第一版代码是：

TreeNode* sortedArrayToBST(vector<int>& nums) { return build(nums, 0, nums.size() - 1); } TreeNode* build(const vector<int>& nums, int left, int right) { if (left > right) { return nullptr; } int mid = left + (right - left) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = build(nums, left, mid - 1); root->right = build(nums, mid + 1, right); return root; }

这里用mid = left + (right - left) / 2而不是(left + right) / 2，是为了防止两个大整数相加时溢出。虽然这道题的数组长度一般不会大到溢出，但这个写法建议养成习惯。

关于“高度平衡”，很多人会有个误判，以为每次取中间元素就会自动平衡。其实高度平衡的关键在于每次划分区间时尽量对半切分，让左右子树的节点数量接近。如果数组有序但每次取中间元素，左右区间长度最多差1，高度差自然就被控制住了。

如果面试官让你写迭代版，思路是用栈模拟递归区间。栈里要同时存三样东西：当前要创建的节点、该节点左子树对应的数组区间、右子树对应的数组区间。初始把根节点和整个数组区间压栈，然后循环弹出，每次创建节点，并把左右区间再压栈。这种写法很容易在压栈顺序上出错，建议先画一遍再用代码实现。

4.2 累加树：反中序遍历的经典现场

LeetCode 538 的题目描述是：把BST中每个节点的值，改成原树中大于或等于该节点值的所有节点值之和。也就是说，每个节点的新值，等于它在原树中序序列里排在它后面的所有节点值之和。

这种题天然适合反过来用中序遍历。我们熟知中序遍历顺序是左根右，遍历结果是从小到大。如果右根左反过来遍历，结果就是从大到小。累加树要求的就是“所有大于等于当前节点的值之和”，用反中序遍历从头累加，第一个节点就是原树最大值，累加值一路递减覆盖每个节点。

递归版本：

class Solution { public: TreeNode* convertBST(TreeNode* root) { int sum = 0; traverse(root, sum); return root; } private: void traverse(TreeNode* node, int& sum) { if (node == nullptr) { return; } traverse(node->right, sum); sum += node->val; node->val = sum; traverse(node->left, sum); } };

这里递归函数的返回值类型是void，因为累加树只是修改节点值，树的结构没有变化，不需要返回新的根。这个判断也再次印证了前面说的：先判断树的结构变不变，再决定返回值。

迭代版用栈模拟反中序遍历，写出来：

TreeNode* convertBST(TreeNode* root) { if (root == nullptr) { return nullptr; } int sum = 0; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { while (cur != nullptr) { st.push(cur); cur = cur->right; } cur = st.top(); st.pop(); sum += cur->val; cur->val = sum; cur = cur->left; } return root; }

这题作为一个“换一种遍历顺序就换一种解法”的案例，特别适合用来和前面的路径总和题做对比。路径总和题是前序遍历穿参数往下传，累加树是反中序遍历往上累加状态，两种传递方式正好互补。

4.3 本地自测方法

刷题网站能即时判题很方便，但本地自测的能力也不能丢。以累加树为例，我分享一个简单的本地自测流程：

第一步，先用数组构造一棵BST。最省事的方法是写一个辅助函数，循环调用BST插入节点的逻辑，把数组元素逐个插进去。

第二步，写一个中序遍历函数，每遍历一个节点就打印node->val加空格。变换前后各打印一次，变换后的中序遍历结果应该仍然是升序，并且每个节点的值是从原中序序列末尾往前累加的结果。

第三步，检查边界值。比如树只有一个节点，累加后该节点值不变，因为只有它自己大于等于它。树的最右下方节点（原树最大值）值也不变，因为它后面没有更大节点。

我经常看到有人刷累加树这题直接提交一次过，但让他打印一遍中序序列验证一下就懵了。本地自测的意义就在这：不是证明代码能跑，而是证明你的思路真正符合题目的数学定义。

5. 常见问题与调试记录

5.1 删除节点后，原根节点被遗漏

删除BST节点最典型的错误是：递归调用了deleteNode(root->left, key)，但没有把返回值接住，导致删除后的新子树根本没有被链接回当前节点。

错法长这样：

if (key < root->val) { deleteNode(root->left, key); // 返回值丢了，删完没接上 }

对的做法一定是：

if (key < root->val) { root->left = deleteNode(root->left, key); }

这个问题我几乎每次讲递归删除题目都会强调。原因在于，递归函数在没有目标节点的路径上只做“往下走”的动作，返回值就是当前节点本身，接不接都一样。但一旦目标节点真的在左子树里，且它的删除导致子树根节点发生变化，这一层如果不接返回值，整棵树的链接就断了。

一个简单的排查方法是：删除叶子节点后，打印整棵树的中序序列，如果原来的值仍然存在，基本就是返回值没接住。

5.2 传引用与返回指针怎么选

有些读者会问：那我把函数签名改成void deleteNode(TreeNode*& root, int key)，不就不需要接返回值了吗？

确实可以。传引用可以直接修改上一层持有的指针，不需要借助返回值。写成这样：

void deleteNode(TreeNode*& root, int key) { if (root == nullptr) return; if (key < root->val) { deleteNode(root->left, key); } else if (key > root->val) { deleteNode(root->right, key); } else { TreeNode* old = root; if (root->left == nullptr) { root = root->right; } else if (root->right == nullptr) { root = root->left; } else { TreeNode* cur = root->right; while (cur->left) cur = cur->left; cur->left = root->left; root = root->right; } delete old; } }

这段代码的好处是不用担心返回值写到一半被忽略，坏处是C++新手看到TreeNode*&这种引用语法会紧张。我自己的建议是：刷题阶段用返回值更通用，因为很多题目框架在原生代码已经写好了返回值签名，直接改传引用反而要处理函数签名匹配问题。传引用写法更适合工具函数内部封装，比如封装一个BST的公共删除接口。

5.3 递归栈溢出与压测

二叉树题目写多了之后，会有一个容易被忽略的问题：递归深度不是你想当然的 O(log n)。如果BST是平衡的，递归深度确实是 O(log n)；但如果输入的序列是有序的，比如数组是 [1, 2, 3, 4, 5]，按顺序插入BST，树会退化成一条单链表，递归深度就变成 O(n)。

节点数量一大，比如十万个，递归栈就会爆。我自己测试过，在一台默认栈大小的机器上，顺序插入构造一棵深度约十万的树，再用递归删除或递归遍历，必挂。

这种情况下有几个思路：

1. 把递归改成迭代，用显式栈模拟，栈上空间可以自己控制。
2. 把输入数组打乱再建树，在练习阶段测通即可，实际项目里BST树本身有平衡机制，不会出现这种崩溃。
3. 小规模压测时先输出树的深度，确认测试环境没有异常。

这也能解释为什么工程上几乎没有人直接用裸BST，而是用红黑树、AVL树这类有自平衡机制的变种。刷题阶段能顺着BST退化成链表的思路联想到平衡树，面试观感会好很多。

5.4 BST类题目通用调试速查表

下面这张表是我刷BST系列题目时反复用到的排查清单，也分享给你：

这张表不用背，写代码遇到问题的时候打开对照着看，几次之后自然就有感觉了。

我自己在删了这一轮BST题目之后，最大的体会是：四道题虽然各自花样不同，但解题前先想清楚两件事——递归该往哪个方向走，以及这一层递归结束后要向上返回什么。只要这个框架立住，代码即使有一两个小细节写错了，调试起来也很快。怕的是一上来就凭感觉写，写完之后连自己都说不清每一步在干什么。

最后再分享一个实战时的小习惯：每写完一道BST题目，用代码打印一遍中序序列。BST的中序序列永远是升序的，如果打印出来不是升序，不用怀疑，代码一定在某个地方破坏了树的有序性。这个验证习惯能帮你省下大量调试时间，也是我从一开始刷二叉树到现在一直保留的操作。