LeetCode - 二叉搜索树的范围和
LeetCode第938题，难度简单。
原题地址：https://leetcode-cn.com/problems/range-sum-of-bst/
题目描述：
给定二叉搜索树的根结点 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
根据二叉搜索树的特质，遍历二叉搜索树。首先判断根节点的值是否在范围内，如果在范围内则加上该节点的值，并接着遍历该节点的左子树和右子树。直到数值超出范围。
再次递归大法好啊。
中文官网题解：
https://leetcode-cn.com/problems/range-sum-of-bst/solution/
个人题解：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
int sum = 0;
if (root == null) {
return sum;
}
if (root.val <= R && root.val >= L) {
sum += root.val;
}
if (root.left != null) {
if (root.left.val >= L) {
sum += rangeSumBST(root.left, L, R);
} else {
sum += rangeSumBST(root.left.right, L, R);
}
}
if (root.right != null) {
if (root.right.val <= R) {
sum += rangeSumBST(root.right, L, R);
} else {
sum += rangeSumBST(root.right.left, L, R);
}
}
return sum;
}
}结果：
一枝独秀. 0ms加100%。emmm..真的只能在很后面的题目上面舒服下了。
