本文主要是介绍938. Range Sum of BST，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
938. 二叉搜索树的范围和
给定二叉搜索树的根结点
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。
解法一
//时间复杂度O(n), 空间复杂度O(logn)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void traversAndCount(TreeNode* root) {if(!root) return;if(root->val > L) traversAndCount(root->left);if(root->val >= L && root->val <= R) sum += root->val;if(root->val < R) traversAndCount(root->right);}int rangeSumBST(TreeNode* root, int L, int R) {sum = 0;this->L = L;this->R = R;traversAndCount(root);return sum;}
private:int sum, L, R;
};思路：
中序遍历，若当前结点值处于[L, R]范围内，就对其求累计和sum。若不是，看其值与L、R的关系遍历左子树或右子树。
最初的代码如下：
traversAndCount(root->left);if(root->val >= L && root->val <= R) sum += root->val;traversAndCount(root->right);
遍历整个树，意外地比解法一的代码快了100ms（？）。
2019/08/13 22:16
这篇关于938. Range Sum of BST的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
