文章目录
一、题目
1、题目描述
给定二叉搜索树的根结点
root，返回值位于范围 [ l o w , h i g h ] [low, high] [low,high] 之间的所有结点的值的和。
样例输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
样例输出：32
2、基础框架
- C语言 版本给出的基础框架代码如下：
int rangeSumBST(struct TreeNode* root, int low, int high){}
3、原题链接
二、解题报告
1、思路分析
直接遍历一遍二叉搜索树，对于在区间
[
l
o
w
,
h
i
g
h
]
[low, high]
[low,high] 内的数，直接累加到一个全局变量sum上，最后返回sum即可；
2、时间复杂度
需要遍历所有二叉树结点各一次，时间复杂度为 O ( n ) O(n) O(n)。
3、代码详解
int sum;
void rangeSumBSTRecursive(struct TreeNode* root, int low, int high){
if(!root) {
return ;
}
if(low <= root->val && root->val <= high) {
sum += root->val; // (1)
}
rangeSumBSTRecursive(root->left, low, high); // (2)
rangeSumBSTRecursive(root->right, low, high); // (3)
}
int rangeSumBST(struct TreeNode* root, int low, int high){
sum = 0;
rangeSumBSTRecursive(root, low, high);
return sum;
}
- ( 1 ) (1) (1) 先序遍历统计和；
- ( 2 ) (2) (2) 递归访问左子树；
- ( 3 ) (3) (3) 递归访问右子树；
三、本题小知识
二叉搜索树的中序遍历的结果为该二叉搜索树的递增序列。
四、加群须知
相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：