代码随想录算法训练营第21天今天的三道题全部是二叉搜索树669修剪二叉搜索树、108将有序数组转换为二叉搜索树、538把二叉搜索树转换为累加树。如果说前面几天还在熟悉二叉树的各种遍历框架今天的任务就正式进入BST的深水区了。这三道题表面看是三个独立题目实际上都在反复敲打同一个东西——二叉搜索树的“有序性”到底如何被递归利用。对正在跟训练营刷题的朋友来说这一天是个很好的分水岭能把这些题真正吃透后面遇到更复杂的BST题目会顺畅很多。这篇文章就分享一下我在第21天刷这三题时的完整思考过程、代码细节以及踩过的坑。1. 今日三题到底在练什么1.1 为何同一天安排三道二叉搜索树代码随想录训练营的节奏一直是有讲究的前面的题大多在练“遍历框架”前序、中序、后序、层序反复打底子。到了第21天突然连续三道BST题目很多同学会有点懵我自己刚开始也有点不适应。这三道题并不是随便凑在一起的。669是对一棵已经存在的BST做区间修剪核心是利用大小关系判断哪半边子树可以直接丢弃108是给你一个有序数组让你构建一棵平衡BST核心是理解“有序”这个前提条件538则要求把BST改成累加树核心是利用中序遍历的有序性做变体。三道题分别从修改结构、构建结构、更新节点值三个方向切入把BST最常考的几种递归姿势全覆盖了。换句话说这一天不是让你学新算法而是逼你把BST最底层的三条规律吃透左小右大的大小关系、中序遍历的升序性、有序区间与平衡结构之间的对应关系。搞懂这三条后面再做BST的插入、删除、验证、最近公共祖先都会轻松不少。1.2 BST递归的三条底层规律先复习一个基础知识二叉搜索树的定义是对于任意节点左子树所有节点值都小于根节点值右子树所有节点值都大于根节点值。这个性质让BST具备三个可以直接利用的规律。第一个规律是大小关系决定搜索方向。给定一个目标值比当前节点小就往左走比当前节点大就往右走。669题的核心剪枝逻辑就来自这里因为一旦某个节点的值小于区间下限那么它的整棵左子树都不可能满足条件没必要逐个遍历直接放弃左子树即可。第二个规律是中序遍历的结果是升序序列。BST的中序遍历顺序是左、中、右恰好把所有节点从小到大排列。538题用的就是它的反向版本右、中、左的遍历顺序对应降序序列配合累加变量就能一次性完成所有节点的更新。第三个规律是升序数组的中间位置天然是平衡BST的根节点。因为数组有序时取中间值作为根左右两侧区间长度差不会超过1递归构建出的树自然高度平衡。108题正是利用这条规律才不需要额外的旋转操作。这三条规律就是今天的解题钥匙。下面一道题一道题来过。2. LeetCode 669修剪二叉搜索树剪枝不是乱砍2.1 读懂题意为什么不能直接删掉整个子树题目要求是把二叉搜索树修剪到区间[low, high]内所有小于low或大于high的节点都要移除但保留的子树结构仍然要是一棵合法的BST。很多初学者第一反应是遇到一个节点值小于low就返回null遇到大于high也返回null。这个做法错得离谱。举个例子root.val low时当前节点左子树里所有节点更小确实不用看了但当前节点的右子树里可能存在符合条件的节点不能一并砍掉。我这里当时就栽过一次。拿一棵最简单的树来说根节点值为3左孩子00的右孩子22的左孩子1然后根节点右孩子4。要求修剪到[1,3]区间。如果看到0小于1就直接返回null那2和1这两个本来符合区间条件的节点也被误删了。正确做法是0虽然要被移除但它的右子树还需要继续递归修剪修剪完的结果要接回来。所以这道题真正想考的是你是否理解BST中“一条边超界不代表整棵子树超界”只有沿着大小关系连续的一侧超界才能安全丢弃整棵子树。2.2 递归实现与完整代码先把我提交通过的递归版本放出来代码用Java写的思路和代码随想录里的版本一致class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root null) { return null; } // 当前节点小于区间下限 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; } }这个解法的关键点在于前两个if分支里不是返回null而是返回对子树继续修剪的结果。root.val low时根据BST性质左子树所有节点都小于low唯一可能还有保留价值的是右子树所以直接return trimBST(root.right)。root.val high时对称处理递归修剪左子树。当前节点值落在[low, high]区间内时需要修剪左右子树把修剪后的树根重新接到当前节点上。这里务必把递归返回值接住写成root.left trimBST(...)不能只调用不赋值否则剪枝结果就丢了。2.3 我在提交中踩过的坑第一坑忘记接返回值。我一开始写的是trimBST(root.left, low, high)而前面没有赋值结果整个树的结构完全没有变化提交后返回的还是原树。排查了半天才意识到递归修改结构时每一层的返回值都需要通过赋值接回给父节点。第二坑误用中序遍历。我试过先把BST中序遍历成有序数组过滤掉不在区间的值再重新构建BST。这个思路能做出来但多了一次遍历和一次构建空间复杂度明显劣化。LeetCode上这道题更想考的是原地递归修剪不是绕路走数组。第三坑边界值写成公开变量。第一版我在类里定义了int low和int high两个成员变量结果发现递归过程中值没变倒是没什么大问题但可读性很差也容易在类复用时有状态残留。直接通过方法参数传递区间更干净。提示如果面试中遇到这道题先说清楚BST的性质支撑再写递归。面试官很看重“为什么root.val low时可以直接只递归右子树”这层分析而不是直接背代码。3. LeetCode 108将有序数组转换为二叉搜索树3.1 题目理解平衡从哪里来这道题给一个升序排列的整数数组要求转换成一棵高度平衡的二叉搜索树。所谓高度平衡是指每个节点的左右子树高度差不超过1。为什么升序数组取中间值就能保证平衡计算一下假设数组长度为n取中间位置mid作为根节点左半部分长度约为n/2右半部分长度也约为n/2两侧子数组长度差最多为1。对左右子数组递归做同样的操作每个子树的左右规模始终不会差太多整棵树的高度自然就是O(log n)。反过来想如果每次取的不是中间值比如始终取最左边的元素作为根那么BST会退化成一条链高度变成O(n)。这就违背了平衡条件。所以这道题的关键不是“怎么构建BST”而是“怎么让构建出来的树保持平衡”。3.2 递归构建的代码与区间边界我采用的是左闭右闭区间的写法也就是区间[left, right]内的元素都还没有被处理class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { if (left right) { return null; } // 防止溢出的中点计算公式 int mid left (right - left) / 2; TreeNode node new TreeNode(nums[mid]); node.left build(nums, left, mid - 1); node.right build(nums, mid 1, right); return node; } }边界条件用的是left right表示当前区间没有元素了返回null。这个判断很重要如果写成left rightmid - 1或mid 1会越界表达式导致无限递归。mid的计算我写成了left (right - left) / 2而不是(left right) / 2。两者的结果在大多数情况下一样但前者可以避免left和right都很大时整数相加溢出。在LeetCode的测试用例里其实很难遇到溢出面试时解释一下这个防溢出细节反而能让面试官觉得你底子扎实。3.3 一个容易忽略的细节区间语义要统一刷题时常见的错误是混用区间语义。比如前半段用左闭右闭[left, right]递归时却不知不觉写成了[left, mid]而不是[left, mid - 1]导致mid这个元素被重复使用构建出的树包含重复节点。我有一个小技巧写递归构建类题目时先明确“当前区间是否是闭区间”然后严格按照这个语义写子区间。左闭右闭时左右子区间分别是[left, mid - 1]和[mid 1, right]如果改成左闭右开[left, right)子区间就是[left, mid)和[mid 1, right)。区间语义不一致代码写得再流畅也是白搭。这道题还可以用迭代方法模拟递归栈来写但意义不大因为递归代码足够清晰面试时用递归是最省时间的。如果你对递归比较担心可以额外练习一道类似的题LeetCode 654最大二叉树思路几乎一样区别只是找最大值的逻辑。4. LeetCode 538把二叉搜索树转换为累加树4.1 累加树与原树的对应关系这道题要求对每个节点将它的值更新为“原树中大于或等于该节点值的所有节点值之和”。乍看有点绕翻译一下就清楚了每个节点的新值等于从最大节点开始一路累加到当前节点的总和。BST一旦中序遍历输出就是升序序列。反过来如果按照右、中、左的顺序遍历输出就是降序序列先访问最大的节点再访问次大的节点依此类推。维护一个累加变量sum每遍历到一个节点就把当前节点的值加到sum上再把sum赋给当前节点就能保证每个节点都得到所有不小于它的节点值之和。画一棵树立刻明白。假设BST是4 / \ 1 6 / \ / \ 0 2 5 7 \ 3中序遍历结果是0, 1, 2, 3, 4, 5, 6, 7。反中序遍历是7, 6, 5, 4, 3, 2, 1, 0。累加过程模拟一下遍历到7累积值77的新值变成7遍历到6累积值136的新值变成13遍历到5累积值185的新值变成18遍历到4累积值224的新值变成22遍历到3累积值253的新值变成25遍历到2累积值272的新值变成27遍历到1累积值281的新值变成28遍历到0累积值280的新值变成28结果完全符合题目要求。理解这个推导过程比死记“反中序遍历累加”这句口诀重要得多。4.2 递归实现与全局变量的处理class Solution { private int sum 0; public TreeNode convertBST(TreeNode root) { if (root null) { return null; } // 右 convertBST(root.right); // 中 sum root.val; root.val sum; // 左 convertBST(root.left); return root; } }这里最大的坑是sum变量。我第一次尝试是用int作为参数传给递归函数写着写着发现问题Java方法参数是值传递递归回到上一层时sum的修改不会被保留。举个例子右子树递归累加完sum变成7回到当前节点时如果sum传的是值类型它仍然是进入递归前的初始值累加结果全丢了。解决办法就是把sum定义为类的成员变量也就是全局变量让所有递归调用共享同一个变量。训练营里很多人会在这一步卡住其实理解了值传递和引用传递的区别问题就迎刃而解。返回值方面这道题可以选择返回TreeNode也可以返回void。我习惯返回TreeNode并返回root因为在LeetCode模板里原方法需要返回TreeNode虽然实际用不上。返回void的写法也能通过思路完全一样。4.3 迭代写法可以怎么扩展如果面试官要求非递归实现可以用栈模拟反中序遍历代码如下class Solution { public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode cur root; DequeTreeNode stack new ArrayDeque(); while (cur ! null || !stack.isEmpty()) { // 先一路往右走把右侧节点入栈 while (cur ! null) { stack.push(cur); cur cur.right; } cur stack.pop(); sum cur.val; cur.val sum; cur cur.left; } return root; } }这段代码用显式栈模拟了递归调用栈外层while控制整体遍历内层while负责把右子树全部压栈。弹栈时处理当前节点然后转向左子树。理解这个迭代版本对后续做中序迭代遍历也有帮助。提示遇到“修改树节点值”的题目优先想遍历顺序。遍历顺序决定业务逻辑业务逻辑决定遍历方式。538能用反中序核心是因为BST的中序有序性。5. 三题串起来BST递归的三种典型姿势5.1 返回值怎么用对比表格训练营第21天刷完这三道题之后我发现一个很有意思的现象三道题都是递归但递归返回值的用法完全不同。把它们放到一起对比非常清晰题号核心操作遍历顺序返回值用途状态变量669修剪前序返回修剪后的子树根用于接回父节点无108构建前序返回新建的子树根用于构建父节点连接无538更新节点值反中序返回值用不上靠全局sum累积成员变量sum669和108虽然都是“返回子树根”但669是修改原树结构后把结果返回给父节点108则是一边新建节点一边返回给上层。两者的共同点是递归修改或构建树结构时返回子树根是一种通用模式可以有效避免父节点丢失子节点引用。538则完全不同它不需要上层利用返回值只需要在遍历过程中不断更新节点值所以用全局变量配合反中序遍历即可。这里我总结出的经验是写递归前先想清楚返回值到底给谁用、要不要用。用不上时强行返回Node反而容易把自己绕晕。5.2 遍历顺序的选择逻辑三道题分别用了不同的遍历顺序。669用前序遍历因为要先判断当前节点值在不在区间内再决定是否递归以及递归哪个方向的子树。108本质上也是前序先创建根节点再递归构建左右子树。538则必须用反中序遍历因为累加依赖“先处理更大的节点”这个顺序。判断用哪种遍历顺序可以问自己一个问题当前节点的处理是否依赖左右子树的处理结果如果依赖子树的返回值通常用后序遍历如果先处理根节点再递归用前序如果需要利用BST的升序或降序特性就用中序或反中序。这个判断方法对绝大多数二叉树题目都适用不只是今天这三道题。5.3 从三道题看BST条件反射刷到第21天我逐渐形成了一套应对BST题目的快速反应流程。看到一棵BST先问自己三件事第一能否利用大小关系剪枝。比如题目要求查找某个范围、最近公共祖先、删除节点这些场景下“比根大往右、比根小往左”的规律能显著降低递归规模。第二中序序列能否提供关键信息。BST中序一定有序凡是涉及第k小、累加、区间和、验证BST合法性等问题优先想到中序遍历。第三递归过程中需要返回什么。是返回子树根、返回布尔值、返回个数还是完全不需要返回值。把返回值想清楚代码结构就定型了大半。这三板斧对初学阶段特别实用。很多题不是不会写递归而是没有形成一个稳定的分析框架想到哪写到哪最后写出了各种边界错误。建议你也把这几个问题写在笔记开头做题前先过一遍。6. 训练营实录常见问题与排查技巧6.1 问题速查表我把今天做题时遇到的、以及训练营群友常问的问题整理成一个速查表方便对照排查现象可能原因排查与解决669提交后树没有变化递归调用了trimBST但没有把返回值赋给root.left或root.right检查是否写成root.left trimBST(...)669删掉了本应保留的节点当前节点超界时直接返回null没有递归处理另一侧子树root.val low时返回trimBST(root.right)不是null108栈溢出或超时循环区间没正确缩小mid被重复使用检查区间语义左闭右闭时右区间从mid 1开始108构建的树不平衡取mid时随机偏移或没有取中间下标mid left (right - left) / 2538节点值累加错误sum定义为局部变量值传递导致递归间不共享把sum提升为成员变量或全局变量538遍历顺序写错写成中序而非反中序累加方向不对先递归右子树再处理当前节点最后递归左子树6.2 写递归的三个自检问题我自己写BST递归时提交前会按下面三个问题做自查基本能挡住大多数低级错误。第一个问题终止条件够吗大多数时候是root null就返回但有些题还需要处理叶子节点特殊情况比如求最小深度时就不能只写root null。第二个问题每一个分支都利用了BST性质吗如果代码里出现对某个非空节点同时向左向右递归但中间没有任何if根据节点值做判断那大概率没有吃透BST的特点。当然有的题确实需要遍历全部节点但至少你要能说出“这里为什么不能利用大小关系剪枝”。第三个问题返回值接住了吗在结构修改类题目中递归返回的新子树根需要通过赋值接回给父节点。遗漏赋值是BST题目最高频的错误来源没有之一。6.3 刷题手感小结今天这三道题结束后我最大的感受是BST题目真的不能凭感觉写。代码随想录训练营前几天的二叉树题目很多是模板题套遍历框架就能过。但今天的669和538光套框架不够必须理解BST的有序性对递归方向、遍历顺序的限制否则代码怎么看怎么别扭。说一个我自己的小习惯每道题AC之后我都会在题解评论区翻一下有没有迭代版本或者更简洁的写法。今天538的迭代版本就是用栈模拟反中序遍历写完后对“遍历顺序即业务逻辑”这句话理解又深了一层。另外建议把669、108、538这三道题放到同一天复习因为它们对BST性质的利用方式完全不同很适合用来检验自己是否真的理解了BST。如果你今天也被这三道题卡到怀疑人生不用太焦虑。把递归展开到小树上手动模拟一遍执行过程多模拟几个用例思路自然会清晰起来。我个人的经验是二叉树的递归写不出来的时候千万别硬写代码先在纸上画一棵树把递归调用关系标清楚代码往往就呼之欲出了。