LeetCode938-二叉搜索树的范围和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/range-sum-of-bst/

中文链接：https://leetcode-cn.com/problems/range-sum-of-bst/

题目详述

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

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

示例 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。

题目详解

  • 如果当前结点值小于 L，说明左子树所有结点值也小于 L，处于区间 [L, R] 的结点可能在右子树，往右子树递归。
  • 如果当前结点值大于 R，说明右子树所有结点值也大于 R，处于区间 [L, R] 的结点可能在左子树，往左子树递归。
  • 如果当前结点值处于区间 [L, R]，左右子树均有可能存在处于区间 [L, R] 的结点，左子树和右子树均要递归。
1
2
3
4
5
6
7
8
9
10
11
public class LeetCode_00938 {

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) {
            return 0;
        }
        if (root.val < L) return rangeSumBST(root.right, L, R);
        if (root.val > R) return rangeSumBST(root.left, L, R);
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }
}