Leetcode 938 Range Sum of BST

发表于 |

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。

示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23

提示：

  1. 树中的结点数量最多为 10000 个。
  2. 最终的答案保证小于 2^31。

题意分析：
在一个二叉搜索树中找到所有的值在L,R范围的节点的值的和。

思路分析：
这道题真是easy中的easy，要是实在不会用递归，也可以先把整个树遍历一遍，用一个O(n)的空间把所有节点值存下来，然后一个个数都行。

当然，在这里肯定还是要用递归的。
不过，说实在的，我们看到树中的节点数量达到10000个，如果最坏情况，讲道理递归是会爆栈的。但是这里可能数据强度没那么大，所以递归可行。

1
2
3
4
5
6
7
8
9
10
11
12
# 248ms
class Solution(object):
    def rangeSumBST(self, root, L, R):
        if not root: return 0
        if root.val < L:
            return self.rangeSumBST(root.right, L, R)

        elif root.val > R:
            return self.rangeSumBST(root.left, L, R)

        else:
            return root.val + self.rangeSumBST(root.left, L, root.val-1) + self.rangeSumBST(root.right, root.val+1, R)