常规解法，递归遍历二叉搜索树的每个元素，然后将符合条件的元素相加。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
int sum = 0;
if(NULL == root)
{
return sum;
}
if(root->val >=L && root->val <=R)
sum += root->val;
int left = rangeSumBST(root->left,L,R);
int right = rangeSumBST(root->right,L,R);
return sum + left + right;
}
};运行结果性能数据：
Runtime: 300 ms, faster than 11.61% of C++ online submissions for Range Sum of BST.
Memory Usage: 65.3 MB, less than 6.48% of C++ online submissions for Range Sum of BST.结果也符合预期，这里因为我们多遍历了很多元素，所以下面的优化方法可以从减少遍历元素着手。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rangeSumBST(TreeNode* root, int L, int R) {
int sum = 0;
if(NULL == root)
{
return sum;
}
if(root->val >=L && root->val <=R)
sum += root->val;
if(root->val > L)
sum += rangeSumBST(root->left,L,R);
if(root->val < R)
sum += rangeSumBST(root->right,L,R);
return sum;
}
};
递归调用左子树和右子树时，如果根节点的值大于等于L，意味着就没有必要遍历左子树（左子树所有的值都小于根节点），相同的道理，如果根节点大于等于R，那么只用遍历左子树即可。
性能运行结果：
Runtime: 164 ms, faster than 98.81% of C++ online submissions for Range Sum of BST.
Memory Usage: 65.1 MB, less than 12.18% of C++ online submissions for Range Sum of BST.