Range Sum of BST
二叉搜索树按层序存储在数组 tree 中：根节点位于索引 0 处，索引为 i 的节点的左子节点和右子节点分别位于 2*i+1 和 2*i+2 处，-1 表示空位置。在二叉搜索树中，节点左子树中的每个值都小于该节点的值，右子树中的每个值都大于该节点的值。
返回所有满足 low ≤ v ≤ high 的节点值 v 的总和；如果没有这样的值，则返回 0。
函数
- treeinteger-array
- 按层序遍历的二叉搜索树，空位用 -1 表示
- lowinteger
- 要计数的最小值
- highinteger
- 要计数的最大值
- 返回值integer
- low 和 high 之间的节点值之和，包含两端
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或者是满足0 ≤ tree[i] ≤ 105的值。 tree[0]永远不会是-1，因此这棵树至少有一个节点。- 数组末尾可能会在最后一个节点之后多出一些
-1条目。 - 空位置的两个子节点也都是空的，而且深度最多为
14。 - 这棵树是有效的二叉搜索树，因此其中所有值都不相同。
0 ≤ low ≤ high ≤ 105- 答案符合 32 位有符号整数的范围。
示例
- 输入
- tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
- 输出
- 88
- 解释
- 从
9到31的值有10、12、15、20和31，它们的总和是88。3、8和40不在这个范围内。
- 输入
- tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
- 输出
- 0
- 解释
- 这棵树中有
25、50和75，它们都不在60和70之间，所以总和是0。四个-1表示25和75的空子节点位置。
- 输入
- tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
- 输出
- 4
- 解释
- 当
low和high都是4时，只有值为4的节点才符合条件。索引为4的4是2的右子节点，因此答案是4。
进阶
如果你需要在同一棵树上回答数千个不同的 (low, high) 查询，怎样才能在 O(log n) 时间内回答每个查询？
提示
逐个打开提示，每个都会多透露一点。
遍历每个节点并将范围内的值相加，就能得到正确答案。搜索树的顺序能告诉你一个节点下的值有什么特点？
节点左子树中的所有值都小于该节点，右子树中的所有值都大于该节点。如果节点的值小于或等于
low，它左侧的任何值可能在范围内吗？从根节点开始，用一个索引栈遍历这棵树。节点值在范围内时，将其加入结果；只有当节点值大于
low时，才将其左子节点的索引2*i+1入栈；只有当节点值小于high时，才将其右子节点的索引2*i+2入栈。
题解
遍历每个节点并累加范围内的值是正确的。利用搜索树的顺序，你可以少做一些工作：节点的值会告诉你较小值和较大值分别在哪一侧，因此不会打开无法包含范围内值的子树。
访问每个节点
思路
只有当子节点的索引在数组范围内，且该位置的值不是 -1 时，它才是真实存在的。在第一个示例中，索引 4 处的 12 在索引 9 和 10 处分别有 10 和 15，而索引 2 处的 31 在索引 5 处的左侧位置为空。
范围内的每个值都位于某个节点中，因此，遍历栈中所有节点，并将满足 low ≤ v ≤ high 的值相加，就能得到正确的总和。这种方法忽略了搜索树的顺序，因此即使范围内只有少数几个值，也会访问全部 n 个节点。
算法
- 将根索引
0压入栈，并设置total = 0。 - 弹出索引
i。如果low ≤ tree[i] ≤ high，则将tree[i]加到total中。 - 当
2*i+1和2*i+2在数组范围内且不为-1时，将它们压入栈。 - 栈为空时，返回
total。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append(left)
if right < n and tree[right] != -1:
stack.append(right)
return total按照搜索树的顺序修剪
思路
节点的左子树中只有小于 v 的值。如果 v ≤ low，其中没有值落在范围内，因此跳过该子树。如果 v ≥ high，右子树中只有大于 high 的值，因此跳过右子树。在第一个示例中，31 等于 high，所以它的右子节点 40 不会被压入。8 小于 low，因此跳过它的左子节点 3，但会访问右子节点 12，因为介于 8 和 20 之间的值可能落在范围内。
你会访问范围内的 k 个值，以及从根节点出发的至多两条路径上的节点：深度为 h 时，时间复杂度为 O(h + k)。当范围覆盖整棵树时，时间复杂度仍为 O(n)。
算法
- 将根节点索引
0压入栈中，并设置total = 0。 - 弹出索引
i，并读取v = tree[i]。如果low ≤ v ≤ high，就将v加到total中。 - 如果
v > low，并且左子节点确实存在，就将它的索引2*i+1压入栈中。 - 如果
v < high，并且右子节点确实存在，就将它的索引2*i+2压入栈中。 - 栈为空时，返回
total。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
# Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
if value > low and left < n and tree[left] != -1:
stack.append(left)
if value < high and right < n and tree[right] != -1:
stack.append(right)
return total
易错点和边界情况
- 使用严格比较。范围的两端都要计入，因此第三个示例中，
low = high = 4时，必须计入4。 - 过早剪枝。在
v = low时，可以剪掉左子树；但在v = low + 1时，左子树中可能包含low本身。 - 丢弃范围外节点的两侧子树。第一个示例中的
8小于low，但它的右子树中有10、12和15。 - 读取数组末尾之后的子节点。读取前检查
2*i+1 < tree.length，并将-1视为没有子节点。 - 在 Lua 和 R 中，数组从 1 开始：节点索引仍使用从 0 开始的编号，以便进行
2*i+1运算，并读取tree[i + 1]。
常见问题3
BST 范围求和的时间复杂度是多少？
剪枝后的遍历会访问范围内的 k 个节点，以及从根节点出发的至多两条路径上的节点：对于深度为 h 的树，时间复杂度为 O(h + k)；当所有值都在范围内时，时间复杂度为 O(n)。栈或递归占用 O(h) 的空间。
可以用中序遍历解决二叉搜索树的范围和问题吗？
是的。中序遍历会按递增顺序列出各个值，因此，当值达到 low 时，就将其加入；遇到第一个大于 high 的值时，就停止遍历。提前停止可以减少对树右侧的处理，而剪枝可以减少对两侧的处理。
求二叉搜索树的范围和时，应该使用递归还是栈？
两种方法都可行。这里的深度最多为 14，所以递归层数较浅。对于有数千层的高树，使用显式栈可以避免触及递归深度限制。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def rangeSumBST(tree, low, high):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
预期输出
88