【每日编程-442期】Leetcode.938二叉搜索树的范围和
root
，返回
L
和
R
（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
样例一：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
样例二：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
解决方法：
（1）算法的基本思想：
一开始没懂题意，看了题友的解答才知道。
找出该树中所有val值在L和R （含）之间的节点，求其和即可。
题目给的是二叉搜索树，二叉搜索树的定义如下：
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
递归即可。
（2）代码实现：
/**
* 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:
int rangeSumBST(TreeNode* root, int L, int R) {
//根
if(!root) return 0;
//当前节点的val值比L还小，则左子树不必再遍历了，遍历右子树即可
if(root->val<L){
return rangeSumBST(root->right,L,R);
}
//右
else if(root->val>R){
return rangeSumBST(root->left,L,R);
}
//
else
return rangeSumBST(root->left,L,R)+rangeSumBST(root->right,L,R)+root->val;
}
};
样例一：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
样例二：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
}
};