我们这个系列的二叉树刷题已经走到了第十五期。能坚持到这一步的读者大概率已经刷过了前序遍历、中序遍历、后序遍历、层序遍历、翻转、对称、路径总和这些基础关口。但二叉树的知识远不止这些真正在面试里拉开差距的往往是从二叉搜索树这一族题目开始的。这一期的题目组合很特别删除二叉搜索树中的节点、修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转成累加树。四道题四个完全不同的操作场景却共用同一套递归能力。你只要把这四道题吃透二叉树部分百分之八十的变形题都不会再慌。这篇文章适合两类读者一类是刷完二叉树基础题、准备系统强化二叉搜索树的同学另一类是已经写过不少题、但遇到“删除节点后要返回新树根”这类问题时还会卡壳的开发者。我会尽量把每一步的“为什么”讲清楚因为这类题目最怕的不是代码写不对而是写完不知道自己为什么对。开头先给一个我个人判断如果你能独立写清楚“删除二叉搜索树节点”这一题并讲明白递归返回值什么时候必须接住、什么时候可以忽略那你对二叉树递归的理解就已经超过了绝大多数候选人。为什么这一题这么关键往下看你就会明白。1. 第十五期的选题思路为什么把四种经典变式放在一起1.1 这一期刷什么删除、修剪、构树、累加先把这四道题摆在一起做一个全景对比题目输入结构输出结构核心操作遍历顺序删除二叉搜索树中的节点BST 目标值BST的根节点找到节点并调整子树递归搜索方向由值决定修剪二叉搜索树BST 区间 [low, high]修剪后BST的根节点删除所有不在区间内的节点前序递归剪枝将有序数组转换为二叉搜索树升序数组高度平衡的BST用中点为根递归建树前序/分治把二叉搜索树转为累加树BSTBST每个节点值为原后缀和反中序累加右、根、左单纯看题目描述好像每一道都在考不同的事情删除考的是指针调整修剪考的是区间判断构造考的是分治累加考的是遍历顺序。但你把它们放在一起做一遍就会发现所有题目都围绕着一个核心问题——递归到底要返回什么。删除和修剪返回新树的根节点构造题用递归返回每棵子树的新根累加树虽然不改变树的结构但递归时也要考虑当前累加值的传递方式。只要能把“递归返回值”这条主线想明白这四道题就是一套连贯练习而不是四道孤立的题。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 迭代版怎么处理面试的时候如果你已经写了递归版面试官再追一句“那你用迭代写一遍”不少人是会卡住的。删除节点的迭代版关键点在于递归版利用调用栈记住了父节点迭代版必须自己记录父节点。迭代版的思路可以拆成两步先用一个指针cur从根出发按BST搜索规则找到值等于 key 的节点同时用parent记录它的父节点。删除节点后要把新的子树根可能是被删节点的左孩子、右孩子或者经过调整后的右孩子接回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(vectorint nums) { return build(nums, 0, nums.size() - 1); } TreeNode* build(const vectorint 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; stackTreeNode* 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)。节点数量一大比如十万个递归栈就会爆。我自己测试过在一台默认栈大小的机器上顺序插入构造一棵深度约十万的树再用递归删除或递归遍历必挂。这种情况下有几个思路把递归改成迭代用显式栈模拟栈上空间可以自己控制。把输入数组打乱再建树在练习阶段测通即可实际项目里BST树本身有平衡机制不会出现这种崩溃。小规模压测时先输出树的深度确认测试环境没有异常。这也能解释为什么工程上几乎没有人直接用裸BST而是用红黑树、AVL树这类有自平衡机制的变种。刷题阶段能顺着BST退化成链表的思路联想到平衡树面试观感会好很多。5.4 BST类题目通用调试速查表下面这张表是我刷BST系列题目时反复用到的排查清单也分享给你现象常见原因调试切入点删除后树丢了部分节点左右孩子都在时没有把左子树挂到右子树最左下角打印删除前后的中序序列看缺失值递归删除后树形态没变递归返回值没接住检查root-left 是否漏写修剪后出现低于low的节点边界判断写成了或检查是否把等于边界值的情况错误剪掉构造的树高度不平衡取中点写成了固定nums.size()/2没考虑左右区间检查是否用区间左右端点计算中点累加树结果不对遍历顺序写成了中序而不是反中序先打印反中序序列确认递减打印中序序列不是升序树的结构在操作过程中被破坏画图对比指针指向这张表不用背写代码遇到问题的时候打开对照着看几次之后自然就有感觉了。我自己在删了这一轮BST题目之后最大的体会是四道题虽然各自花样不同但解题前先想清楚两件事——递归该往哪个方向走以及这一层递归结束后要向上返回什么。只要这个框架立住代码即使有一两个小细节写错了调试起来也很快。怕的是一上来就凭感觉写写完之后连自己都说不清每一步在干什么。最后再分享一个实战时的小习惯每写完一道BST题目用代码打印一遍中序序列。BST的中序序列永远是升序的如果打印出来不是升序不用怀疑代码一定在某个地方破坏了树的有序性。这个验证习惯能帮你省下大量调试时间也是我从一开始刷二叉树到现在一直保留的操作。