手稿_V1.0159
需积分: 0 23 浏览量
2022-08-03
15:06:43
上传
评论
收藏 184KB PDF 举报
分析:
二叉搜索树本身满足一些性质:当前节点左侧的值不大于当前节点的值，当前节点右侧的值不小于
当前节点的值，又题设中"二叉搜索树保证具有唯一的值。",所以性质中都取不到等号.
根据以上性质:可以使用递归方法先序遍历的方法遍历二叉搜索树中在[L,R]之间的元素，并累加返
回即可.
同理使用栈结构辅助即可使用迭代方法遍历二叉搜索树.
方法一:C_递归遍历
/*
给定二叉搜索树的根结点 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
提示：
树中的结点数量最多为 10000 个。
最终的答案保证小于 2^31。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int ret_val = 0;
void __preOrderTravel(struct TreeNode* node , int L , int R)
{
if(node==NULL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
评论0