LeetCode 938简单二叉树 · BST
二叉搜索树的范围和 图解题解
这道题到底在问什么
给一棵二叉搜索树的根 root 和两个整数 low、high,返回所有满足 low ≤ 节点值 ≤ high 的节点值之和。
- 树
- [10,5,15,3,7,null,18]
- low / high
- 7 / 15
- 输出
- 32 (= 7 + 10 + 15)
先想最直接的笨办法
这就是整棵 BST。中序读出来是 3 5 7 10 15 18,严格升序,确实是合法 BST。先用笨办法演一遍:每个节点都走、都比一次。（动画第 7 步）
最优解：一步一步想明白
- 3这样也能得到正确答案,但白白走了很多根本不可能在区间里的节点(比如一整棵全是小数的子树)。BST 的有序性被浪费了。
- 4所以站在某个节点上,只看它的值和区间的关系,就能提前判定一整棵子树有没有希望——不用真的走进去。
- 5核心就这三句。val<low 时它的左孩子只会更小,整棵左子树不用看;val>high 时右子树同理。这就是「剪枝」——剪掉整片不可能的枝。
- 6盯住两件事:当前停在哪个节点(橙色)、根据它的值决定累加还是剪掉哪一边。右侧面板记着累计和与决策。
- 7low=7 high=15 sum=0这就是整棵 BST。中序读出来是 3 5 7 10 15 18,严格升序,确实是合法 BST。先用笨办法演一遍:每个节点都走、都比一次。
- 8暴力遍历:全访问笨办法不挑路:先访问根 10,在区间里就加上。但它接下来会两边都钻进去,哪怕明知没希望。
- 9暴力遍历:全访问走到 5,它 <5 不加。聪明做法到这就该剪掉左边,可笨办法偏要继续往左钻。
- 10暴力遍历:浪费果然钻到了 3——它比 5 还小,根本不可能在区间里,这一步完全白走。树越大,这种浪费越多。这就是要剪枝的理由。
- 11low=7 high=15 sum=0看清浪费在哪了。现在重来一遍,这次带上三条剪枝规则,从根 10 出发——同样的答案,少走很多路。
- 1210 在 [7,15] 内 → 累加根 10 落在 [7,15] 里(规则③):把它加进 sum,sum=10。因为可能两边都有合法节点,左右子树都要走。先去左孩子 5。
- 13sum=10 · 下探左孩子 510 变绿表示已累加完。DFS 先深入左边:现在停在节点 5,准备对它做判断。
- 145 < low(7) → 只走右节点 5 比 low(7)还小(规则①)。BST 里 5 的左孩子只会更小,所以节点 3 连同它整棵左子树直接剪掉、不访问(标紫=被剪)。只往右孩子 7 走。
- 153 永不访问 · 转向右孩子 75 自己没落在区间里(它=5<7),所以不累加,只起「导航」作用——把我们带到右孩子 7。节点 3 始终是紫色:这一整次 DFS 它一次都没被碰过。
- 167 在 [7,15] 内 → 累加节点 7 正好等于 low(规则③,边界包含在内)。累加,sum = 10+7 = 17。规则③要左右都走,但它两个孩子都是空。
- 17空节点 → 返回 07 的左右都是空节点(命中递归出口,各返回 0)。所以以 7 为根的整棵子树只贡献它自己 = 7。这条左路彻底走完(7 标绿:已结算)。
- 18sum=17 · 回到根去走右边7 变绿。根 10 的整个左半边都处理完了(只累加了 7,剪掉了 3)。DFS 回到根,转头去走右孩子 15。
- 19DFS 折返,进入右子树左半边的递归全部返回了,带回来的和是 7。控制权回到根 10,现在执行它的第二步——走右孩子。橙色重新落到根上,准备下探 15。
- 2015 在 [7,15] 内 → 累加右孩子 15 正好等于 high(规则③,右边界也算在内)。累加,sum = 17+15 = 32。规则③要左右都走,但 15 没有左孩子,所以去看它的右孩子 18。
- 2115.left = null → 返回 015 标绿(已累加)。它的左孩子是空(返回 0),所以直接转去右孩子 18,准备判断。
- 22sum=32 · 当前 18现在停在 15 的右孩子 18,准备判断它在不在区间内。
- 2318 > high(15) → 只走左节点 18 比 high(15)还大(规则②)。它不累加,而且 BST 里它的右子树只会更大,整棵右边剪掉,只看它的左孩子——左孩子为空,这条路也到底了。
- 24sum=32 · DFS 收尾18 变蓝(访问过但没累加)。到这里 DFS 全部结束:累加了 10、7、15,剪掉了 3、跳过了 18 的右边。
- 25sum = 7 + 10 + 15 = 32绿色是计入答案的 3 个节点(10+7+15=32),紫色 3 是被整棵剪掉、从未访问的子树。靠剪枝,我们少走了路又拿到了正确答案。
- 26这棵树小,差别不大;但若 3 下面挂着几千个更小的节点,剪枝就能一刀剪掉整片,差距是数量级的。这就是利用 BST 有序性的威力。
- 27回看整趟:5 太小只去了右(剪掉 3),18 太大本该只去左(左空),10、7、15 正好在区间内被累加。三条规则把整次遍历完全决定了——下面看代码,会发现就是三个 if。
- 31节点 5 小于 low 却仍递归左 → 白走 3如果在节点 5 小于 low 时不剪枝、照样递归左孩子,节点 3 就会被白白访问一遍(这里标蓝)。它下面若挂着成千上万个更小的节点,就是灾难性的浪费。该剪必剪。
⚠️ 容易写错的地方
✗ 错：val < low 时仍递归左子树
✓ 对：val < low 时只递归右子树
左子树全更小,递归进去纯属浪费(剪枝的意义就没了)
✗ 错：区间判断用 < / > 漏掉边界
✓ 对：用 low ≤ val ≤ high(闭区间)
题目区间含端点,7、15 这种正好卡边界的会被漏加
完整代码（Python / C++ / Java）
Python
class Solution:
def rangeSumBST(self, root, low, high):
if not root: # 空节点 → 贡献 0
return 0
if root.val < low: # 太小,整棵左子树都太小
return self.rangeSumBST(root.right, low, high) # 只走右
if root.val > high: # 太大,整棵右子树都太大
return self.rangeSumBST(root.left, low, high) # 只走左
# low <= val <= high:累加自己 + 左右都走
return (root.val
+ self.rangeSumBST(root.left, low, high)
+ self.rangeSumBST(root.right, low, high))C++
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (!root) 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);
}
};Java
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);
}
}复杂度
时间复杂度
O(n)
最坏(区间覆盖整棵树)每个节点访问一次;剪枝只让实际访问数变少,上界仍 O(n)
空间复杂度
O(h)
递归栈深度 = 树高 h;平衡树 O(log n),退化成链 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树的范围和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 val<low 能直接剪掉整棵左子树?+
BST 性质:左子树所有值都 < val < low,不可能落进区间,整棵无希望。
区间是开还是闭?+
闭区间 low≤val≤high,端点要计入。
能不能用迭代+栈写?+
可以,把递归改成显式栈做 DFS,剪枝逻辑(只压该走的那一边)完全一致。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二叉搜索树的范围和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。