938.二叉搜索树的范围和

发表于 | 分类于
字数统计: 243 | 阅读时长 ≈ 1

一、题目描述

给定二叉搜索树的根结点 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。

二、题解

1.递归

1.1 思路

思路非常简单，递归判断左右子树，符合要求就将值并入sum，最后返回sum

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int rangeSumBST(struct TreeNode *root, int L, int R)
{
    if (root == NULL)
        return 0;
    int sum = 0;
    if (root->val >= L && root->val <= R)
        sum += root->val;
    int l = rangeSumBST(root->left, L, R);
    int r = rangeSumBST(root->right, L, R);
    sum = sum + l + r;
    return sum;
}