二叉搜索树范围和：从暴力遍历到剪枝递归的优化之路

这道题我第一次见到的时候心里想的是“这不就是遍历一遍树求和吗”无非多加一个区间判断。后来在复盘阶段重新做了一遍才发现自己漏掉了二叉搜索树最值钱的性质有序性。你一旦忽略了这一点解法就成了普通二叉树遍历算法复杂度从理论上被锁死在O(n)而面试官真正想看的是你能不能利用左小右大的特性把整棵子树直接排除在搜索范围之外。“二叉搜索树的范围和”是一个典型的考察点题目简单到新手也能五分钟写完但它同时又足够深可以一路问到你“最坏情况复杂度是多少”“能不能把单次查询降到O(logn)”“如果树不平衡会不会爆栈”。这篇文章我想把这道题彻底拆开从题面、三种解法、边界细节、变体扩展、踩坑记录都过一遍。无论你是刚开始刷题、准备面试还是单纯想巩固树和递归的基础这篇文章都应该能给你一点参考。1. 先别急着遍历这道题在考你“用还是不用”BST的性质1.1 题面解读到底要算什么题目给的信息非常短一棵二叉搜索树根节点为root给定两个整数low和high要求返回所有节点值在[low, high]区间内的节点值之和。注意是闭区间也就是说节点值恰好等于low或者恰好等于high的节点也要计入总和。举个例子假设二叉搜索树的结构如下10 / \ 5 15 / \ \ 3 7 18如果low7high15那么符合条件的节点有10、15、7三个它们的值之和是1015732。节点5不在区间内3小于low18大于high全部排除。答案就是32。再看一个稍微复杂一点的例子。如果树是10 / \ 5 15 / \ / \ 3 7 13 18 / / 1 6low6high10那么符合条件的节点有6、7、10总和是671023。这里有两个容易忽略的细节6是节点7的左孩子虽然小于low的父子节点7但它自身刚好在区间边界上必须加上13大于10不能算。跟上个例子的思路一样你要判断的是“节点值本身是否在区间内”而不是“节点在树里的位置是否在某个范围里”。这道题适合谁来练呢对于刚接触二叉树遍历的新手可以用它来巩固递归的三段式写法终止条件、单层逻辑、返回值处理。对于有了一定经验、准备面试的开发者它的价值在于你能不能用最短的时间识别出“BST范围”这个组合背后对应的剪枝思路。1.2 BST的有序性才是这道题的题眼二叉搜索树有一个重要性质对于任意一个节点它左子树上的所有节点值都小于当前节点值右子树上的所有节点值都大于当前节点值。这个性质使得BST在结构上天然携带了排序信息等价于一个“隐式的有序数组”。所以如果当前节点的值已经小于low那么它左子树上的所有节点值一定都小于low整棵左子树不可能有任何节点符合条件如果当前节点的值已经大于high那么它右子树上的所有节点值一定都大于high整棵右子树也可以一次性丢掉。这就和在一个升序数组里做二分查找一样你不需要访问每一个元素只要根据中间位置的值和目标的相对大小决定往哪一半继续搜索。很多人在解这道题时第一版代码用的是无差别的全局递归。在面试官眼里那种写法不是错但属于“没有吃到BST红利”的写法。同样是O(n)的最坏复杂度利用有序性剪枝后平均情况下访问的节点数会少很多代码表达出来的思路也更清晰。你完全可以先说出暴力解再自然地过渡到剪枝版本让面试官看到你的优化过程。2. 三种解法从老老实实到砍掉半棵树2.1 兜底写法全树遍历加值判断首先给出最直观的解法。不使用任何BST性质就是递归遍历每一个节点只要节点值落在[low, high]内就累加。这种写法在普通二叉树上也适用逻辑最简单也最不容易出错。class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root null) { return 0; } int sum 0; if (root.val low root.val high) { sum root.val; } sum rangeSumBST(root.left, low, high); sum rangeSumBST(root.right, low, high); return sum; } }这个解法的时间复杂度是O(n)n是树的节点总数因为每个节点都要访问一遍。空间复杂度是O(h)h是树的高度递归时操作系统栈的深度由递归调用链决定。如果树严重不平衡退化成一条链表h就等于n递归深度可能很大。我把这种写法称为“兜底解”。它的优点是通用性强哪怕把这棵树换成普通的二叉树代码也不用改。缺点是完全没有利用BST的有序性。如果在面试中只给出这一个解法面试官大概率会追问一句既然树是二叉搜索树有没有更高效的做法所以你能写出这个版本只能说及格还要能够继续优化。2.2 中序路线按照升序做一次区间筛选BST有一个广为人知的特性中序遍历的结果是递增序列。把整棵树中序遍历一遍其实就是从左到右扫描一个升序数组。利用这个思路可以在中序遍历的过程中做区间筛选。因为是升序一旦当前节点值已经大于high就能提前终止后续遍历因为后面的节点只会更大。而当节点值小于low时它的左子树也不需要访问可以直接跳到右子树。来看看这个中序剪枝版本class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root null) { return 0; } int sum 0; if (root.val low) { sum rangeSumBST(root.left, low, high); } if (root.val low root.val high) { sum root.val; } if (root.val high) { sum rangeSumBST(root.right, low, high); } return sum; } }这段代码的顺序非常有讲究。先判断root.val是否大于等于low只有满足这个条件才去左子树递归否则左子树所有节点都小于low直接放弃。同理只有root.val小于等于high才去右子树递归。这样每次左右递归都带着一个前提条件访问节点数明显减少。这个方法本质上已经是一种剪枝但它沿用了中序“左-根-右”的遍历顺序每一步都带着区间判断。和前一种写法相比它的优势在于跳过了大量注定不符合条件的子树而且逻辑顺序贴近中序遍历容易理解。不过它依然有一些不必要的访问比如当前节点值落在区间内时左右子树的递归条件其实都是成立的这时它和暴力遍历没有区别。2.3 最优解按区间方向直接剪枝递归既然二叉搜索树的每个节点都已经隐含了“左小右大”的信息最自然的做法就是直接根据当前节点值和low、high的关系决定走向哪一侧。核心逻辑是这样如果当前节点值为空直接返回0如果当前节点值小于low那么当前节点和它的左子树都排出区间只用递归右子树如果当前节点值大于high那么当前节点和它的右子树都排出区间只用递归左子树如果当前节点值在区间内累加当前值并递归左右子树。class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root null) { return 0; } if (root.val low) { return rangeSumBST(root.right, low, high); } if (root.val high) { return rangeSumBST(root.left, low, high); } return root.val rangeSumBST(root.left, low, high) rangeSumBST(root.right, low, high); } }回看前面第一个例子root10low7high15。10在区间内累加10递归左节点5和右节点15。左节点5小于7只递归它的右子树节点77在区间内累加7继续递归它的左右空节点。右节点15在区间内累加15递归右节点1818大于15只递归它的左子树左子树为空。最终得到32。在这个过程里节点3从头到尾没有被访问。原因是当root5被判定为小于low时它的整棵左子树都被跳过了。这就是剪枝的效果你每在一个节点上做一次方向判断就可能丢弃一整棵子树。Python版本同样简洁class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) - int: if not root: return 0 if root.val low: return self.rangeSumBST(root.right, low, high) if root.val high: return self.rangeSumBST(root.left, low, high) return root.val self.rangeSumBST(root.left, low, high) self.rangeSumBST(root.right, low, high)这段代码的返回值设计很巧妙小于low时直接返回右子树的递归结果不需要考虑左侧大于high时直接返回左子树的递归结果不需要考虑右侧在区间内时才把左右子树的结果和当前值一起加起来。这样每个节点的计算路径都是确定且无冗余的。3. 复杂度、边界细节与容易被忽略的坑3.1 复杂度到底怎么算别被“二分”两个字骗了有些同学看到这里会觉得BST里做范围搜索那不就是二分吗复杂度应该是O(log n)这里必须泼一盆冷水剪枝解法在最优情况下确实可以只访问O(logn)个节点但最坏情况仍然是O(n)。什么情况下会退化成O(n)比如low和high覆盖了整棵树所有节点的值那么每一个节点都会落在区间内剪枝条件永远不触发每个节点都必须访问一遍。再比如树退化成了单链表每个节点只有一个孩子这种情况下无论怎么剪枝路径长度都等于n复杂度自然也是O(n)。所以这道题的时间和空间复杂度需要分开说。时间复杂度最坏O(n)平均情况下远小于n具体取决于区间范围大小和树的结构。空间复杂度是O(h)h为树高。在平衡二叉树中hlogn但在极度不平衡的树中hn。这个细节经常被问不要答错。3.2 low和high的边界条件以及一个整数溢出的隐患边界条件主要看这么几个维度。第一个是空树。root为null时说明没有节点可以累加直接返回0。别看这只是一个空指针判断很多初学者在写递归时把“rootnull”放在累加逻辑之后导致空指针异常。第二个是low等于high。这时候题目退化成一个“查找有没有值等于low的节点并返回该值”的问题。如果有多个节点值相同也要全部累加。BST中可能存在重复值吗经典BST通常是不重复的但有些题目定义允许重复需要注意题目的具体约定。第三个是节点值可能出现负数。如果范围是[low, high]且low和high都是负数累加结果也可能是负数求和时不要下意识认定返回值一定是正数。还有一个很多人会踩的坑是整数溢出。题目给出的节点值是int但多个int累加之后可能超过int上限。举例来说如果树很大每个节点值都是10亿级别几百个节点求和后就可能溢出。稳妥的做法是累加变量用long类型最后再转成int返回。class Solution { public int rangeSumBST(TreeNode root, int low, int high) { return (int) dfs(root, low, high); } private long dfs(TreeNode root, int low, int high) { if (root null) { return 0L; } if (root.val low) { return dfs(root.right, low, high); } if (root.val high) { return dfs(root.left, low, high); } return root.val dfs(root.left, low, high) dfs(root.right, low, high); } }3.3 极端树形下的栈溢出问题递归写法虽然简洁但在树高很大的时候比如一棵只有右孩子的斜树递归深度等于节点数很容易触发栈溢出。在线判题系统里通常会给一个默认的栈空间一般几千层深度问题不大但如果节点数量达到十万级别递归就可能崩。这时候可以考虑用迭代加显式栈。不依赖系统递归栈而是自己用一个栈来模拟深度优先遍历每弹出一个节点就按照同样的剪枝逻辑决定压入哪些子树。class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root null) { return 0; } int sum 0; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); if (node null) { continue; } if (node.val low) { stack.push(node.right); } else if (node.val high) { stack.push(node.left); } else { sum node.val; stack.push(node.left); stack.push(node.right); } } return sum; } }迭代版本和递归版本表达的是同一种剪枝逻辑只是把递归调用栈换成了显式的栈结构。真正常见的面试追问是“如果树特别深递归会出什么问题”能顺手写出迭代解法属于加分项。4. 从一道题延伸到一类题三种扩展方向4.1 如果这棵树不是二叉搜索树解法该如何退化面试题往往会在此基础上变形。最简单的一种是把二叉搜索树改成普通二叉树节点之间没有大小关系剪枝条件就全部失效。这时候无论是递归遍历还是中序遍历都必须访问所有节点。这种情况下2.1节里的暴力写法反而是唯一正确的通用解。所以你在讲解自己的思路时可以明确告诉面试官剪枝之所以可行完全依赖于BST的“左小右大”约束。一旦这个约束不成立整个优化就失去了根基。这个表达能体现你对数据结构性质的敏感度。4.2 多次查询场景把范围求和变成前缀和问题如果题目不满足于一次查询而是要求在同一棵树上反复执行很多次范围求和比如Q次查询每次给定不同的low和high那么每次都递归一次显然不划算。更好的思路是利用BST中序序列的有序性先做一次预处理把树节点转成一个升序数组再配合前缀和数组把每次查询的时间复杂度降到O(logn)甚至O(1)。预处理的过程很简单中序遍历BST得到一个升序列表vals。同时维护一个前缀和数组prefix其中prefix[i]表示vals中前i个元素的和数组长度为n1。查询时先用二分查找找到第一个大于等于low的索引L以及最后一个小于等于high的索引R。然后答案是prefix[R 1] - prefix[L]这里索引边界的处理是常见的错误来源。假设vals[3,5,7,10,15,18]prefix[0,3,8,15,25,40,58]。low7high15那么L是7所在的下标2R是15所在的下标4答案是prefix[5]-prefix[2]40-1525对应的节点是7、10、15正好正确。如果low或high在数组范围之外二分查找需要处理不存在的情况通常L是第一个大于等于low的位置R是最后一个小于等于high的位置如果LR区间内没有符合条件的结果直接返回0。这个思路经常出现在“二叉搜索树迭代器”“有序数组区间和”一类进阶题目中属于高频扩展。4.3 更大的数据量还能不能更快进一步想如果树本身是动态的插入和删除操作频繁发生那么每次重新生成升序数组也不现实。这时候可以考虑用平衡二叉搜索树配合每个节点维护的子树节点和来做到动态区间查询。在树的节点中额外记录子树的和查询时依然可以利用当前节点值跟low、high的关系剪枝同时利用子树和快速跳过整棵子树。如果要继续深挖还可以延伸到树状数组或线段树来维护一个可变数组的区间和。这些结构在竞赛题和大型系统设计里都很常见。当然在“二叉搜索树的范围和”这道题里不需要用到这么重的手段但如果你能往这个方向延展聊几句面试官对你的评价会不一样。5. 我踩过的坑和一份排查清单5.1 判题环境与方法签名的小陷阱在线判题平台一般会定义TreeNode类通常是public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }需要注意几点。第一不要在类里定义静态变量来累计求和。因为判题器可能在同一个进程里复用一个类的多个实例静态变量不会自动清零第二个测试用例就会拿第一个用例的残留值继续累加。即使动态语言中类属性也存在类似问题。第二不要试图修改TreeNode的val值来标记访问状态因为多个测试用例可能复用同一个树对象。第三方法命名和返回类型要严格按照题目要求来尤其是当返回值类型是int时你内部用long累加也要在最后转型。5.2 常见错误速查表错误现象可能原因解决办法输出结果比预期大把区间外的节点也累加了比如小于low时递归了左子树当前值小于low只递归右子树输出结果比预期小漏掉了恰好等于low或high的边界节点使用和判断不要写成和结果偶尔是负数累加值超出int范围累加变量用long返回前再转int递归栈溢出树是斜树递归深度过大换用显式栈的迭代解法两个测试用例结果串了用了静态变量或类变量保存结果改成局部变量或参数传递累加结果空指针异常没有判空就访问root.val递归函数开头先判断root null这些错误里前两条是最常见的。尤其是刚接触剪枝的人最容易在“小于low时只递归右子树”这一步写顺手忘记丢弃左子树结果把一堆不符合条件的节点也加进去。5.3 一点实操心得我个人在刷这道题的时候习惯先把树在纸上画出来把low和high两条线标在树旁边然后按照剪枝逻辑手动走一遍。不要小看这个动作很多边界错误在纸上走一遍就能看出来比在调试器里断点半天更高效。我自己踩过最深刻的一次坑是在Python版本里用了全局变量acc结果在同一个测试文件里连续跑多个用例第二个用例的结果永远比预期大。后来才意识到是全局变量没有清零。从那以后我写递归都优先采用“返回值累加”的方式尽量不用外部变量。如果你在面试或者练习中遇到这道题可以这样组织回答先陈述题目定义给一个简单样例然后从暴力全遍历开始说明复杂度O(n)接着引入BST有序性展示剪枝版本最后补上最坏情况复杂度分析和可能的栈溢出风险。一套下来既展示了基础功底也展示了优化意识。这道题虽然不难但它是少数能把“树的遍历”“递归设计”“复杂度分析”串在同一个题目里的入门题值得认真做一遍。