【JavaScript】Leetcode每日一题-二叉搜索树的范围和
【题目描述】
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
示例1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32
示例2：
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23
提示：
树中节点数目在范围 [1, 2 * 10^4] 内
1 <= Node.val <= 10^5
1 <= low <= high <= 10^5
所有 Node.val 互不相同
【分析】
-
思路：
dfs+剪枝
当root.val<low时，剪掉左半边
当root.val>left时，剪掉右半边
-
代码：
// 形式1
var rangeSumBST = function(root, low, high) {
const dfs = function(root){
if(root.left && root.val > low){
dfs(root.left);
}
if(root.val >= low && root.val <= high){
sum += root.val;
}
if(root.right && root.val < high){
dfs(root.right);
}
};
let sum = 0;
dfs(root);
return sum;
};
// 形式2
var rangeSumBST = function(root, low, high) {
const dfs = function(root){
if(!root){
return 0;
}
if(root.val < low){
return dfs(root.right);
}
if(root.val > high){
return dfs(root.left);
}
return root.val + dfs(root.right) + dfs(root.left);
};
return dfs(root);
};