题目描述

[EN | CN]

给定二叉搜索树的根结点 root,返回 LR(含)之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

示例 1:

1
2
输入:root = [10,5,15,3,7,null,18], L = 7, R = 15
输出:32

示例 2:

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

提示:

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

解法 1:递归

题目里写的数据虽然是数组,其实是以 BST(二叉搜索树)保存的,而 BST 中每个结点的左子树都小于自身、右子树都大于自身。因此题目的意思其实是求出 BST 中所有 >= L 且 <= R 的值的和。

这种题的话我们最首先肯定考虑递归,那么在每次递归中:

  • 如果当前结点为 None,返回 0;
  • 如果当前结点值 X < L 时,返回递归调用右子树的结果;
  • 如果当前结点值 X > R 时,返回递归调用左子树的结果;
  • 如果当前结点值 X >= L 且 X <= R 时,返回自身的值 + 左子树结果 + 右子树结果。

复杂度分析略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        if root.val < L:
            return self.rangeSumBST(root.right, L, R)
        if root.val > R:
            return self.rangeSumBST(root.left, L, R)
        return sum([
            root.val,
            self.rangeSumBST(root.right, L, R),
            self.rangeSumBST(root.left, L, R)
        ])
  • 执行用时:264 ms,在所有 Python3 提交中击败了 65.68% 的用户。
  • 内存消耗:21.8 MB,在所有 Python3 提交中击败了 8.33% 的用户。