二叉搜索树的范围和

这样也能得到正确答案,但白白走了很多根本不可能在区间里的节点(比如一整棵全是小数的子树)。BST 的有序性被浪费了。

所以站在某个节点上,只看它的值和区间的关系,就能提前判定一整棵子树有没有希望——不用真的走进去。

核心就这三句。val<low 时它的左孩子只会更小,整棵左子树不用看;val>high 时右子树同理。这就是「剪枝」——剪掉整片不可能的枝。

盯住两件事:当前停在哪个节点(橙色)、根据它的值决定累加还是剪掉哪一边。右侧面板记着累计和与决策。

初始树 · 全部待访问：这就是整棵 BST。中序读出来是 3 5 7 10 15 18,严格升序,确实是合法 BST。先用笨办法演一遍:每个节点都走、都比一次。

笨办法 · 走到 10：笨办法不挑路:先访问根 10,在区间里就加上。但它接下来会两边都钻进去,哪怕明知没希望。

笨办法 · 走到 5：走到 5,它 笨办法偏要继续往左钻。

笨办法 · 白走 3：果然钻到了 3——它比 5 还小,根本不可能在区间里,这一步完全白走。树越大,这种浪费越多。这就是要剪枝的理由。

初始树 · 重新开始：看清浪费在哪了。现在重来一遍,这次带上三条剪枝规则,从根 10 出发——同样的答案,少走很多路。

访问根 · 10：根 10 落在 [7,15] 里(规则③):把它加进 sum,sum=10。因为可能两边都有合法节点,左右子树都要走。先去左孩子 5。

10 已累加：10 变绿表示已累加完。DFS 先深入左边:现在停在节点 5,准备对它做判断。

判断 5 · 触发剪枝：节点 5 比 low(7)还小(规则①)。BST 里 5 的左孩子只会更小,所以节点 3 连同它整棵左子树直接剪掉、不访问(标紫=被剪)。只往右孩子 7 走。

5 剪左 · 3 被跳过：5 自己没落在区间里(它=5不累加,只起「导航」作用——把我们带到右孩子 7。节点 3 始终是紫色:这一整次 DFS 它一次都没被碰过。

判断 7 · 累加：节点 7 正好等于 low(规则③,边界包含在内)。累加,sum = 10+7 = 17。规则③要左右都走,但它两个孩子都是空。

7 的左右孩子 · 都为空：7 的左右都是空节点(命中递归出口,各返回 0)。所以以 7 为根的整棵子树只贡献它自己 = 7。这条左路彻底走完(7 标绿:已结算)。

7 已累加 · 左子树完成：7 变绿。根 10 的整个左半边都处理完了(只累加了 7,剪掉了 3)。DFS 回到根,转头去走右孩子 15。

回到根 · 转向右孩子 15：左半边的递归全部返回了,带回来的和是 7。控制权回到根 10,现在执行它的第二步——走右孩子。橙色重新落到根上,准备下探 15。

判断 15 · 累加：右孩子 15 正好等于 high(规则③,右边界也算在内)。累加,sum = 17+15 = 32。规则③要左右都走,但 15 没有左孩子,所以去看它的右孩子 18。

15 的左孩子 · 为空：15 标绿(已累加)。它的左孩子是空(返回 0),所以直接转去右孩子 18,准备判断。

15 已累加 · 下探右孩子 18：现在停在 15 的右孩子 18,准备判断它在不在区间内。

判断 18 · 触发剪枝：节点 18 比 high(15)还大(规则②)。它不累加,而且 BST 里它的右子树只会更大,整棵右边剪掉,只看它的左孩子——左孩子为空,这条路也到底了。

18 处理完 · 全树遍历结束：18 变蓝(访问过但没累加)。到这里 DFS 全部结束:累加了 10、7、15,剪掉了 3、跳过了 18 的右边。

最终结果：绿色是计入答案的 3 个节点(10+7+15=32),紫色 3 是被整棵剪掉、从未访问的子树。靠剪枝,我们少走了路又拿到了正确答案。

这棵树小,差别不大;但若 3 下面挂着几千个更小的节点,剪枝就能一刀剪掉整片,差距是数量级的。这就是利用 BST 有序性的威力。

回看整趟:5 太小只去了右(剪掉 3),18 太大本该只去左(左空),10、7、15 正好在区间内被累加。三条规则把整次遍历完全决定了——下面看代码,会发现就是三个 if。

雷区实演 · 不剪枝：如果在节点 5 小于 low 时不剪枝、照样递归左孩子,节点 3 就会被白白访问一遍(这里标蓝)。它下面若挂着成千上万个更小的节点,就是灾难性的浪费。该剪必剪。

边界三连：端点要算、空树返 0、区间够大就退化成「全树求和」——这三种边界先想清楚。

面试追问：BST 性质为什么能剪、闭区间、递归转迭代,是这题最常被追问的三点。