英文:
Sum of bst tree nodes with in certain range
问题
Here is the translated code portion:
var rangeSumBST = function(root, low, high) {
let sum = 0;
if (root) {
sum += (root.val >= low && root.val <= high) ? root.val : 0;
sum += rangeSumBST(root.left, low, high);
sum += rangeSumBST(root.right, low, high);
}
return sum;
};
I won't provide translations for the other non-code content.
英文:
var rangeSumBST = function(root, low, high) {
let sum=0;
if(root){
sum+=(root.val>=low&&root.val<=high)?root.val:0;
sum+=rangeSumBST(root.left,low,high);
sum+=rangeSumBST(root.right,low,high);
}
return sum;
};
This is the function to find sum of values between certain range.
My doubt here is if we give sum =0 everytime it won't be initialized to zero.
Can anyone help me in understanding recursion concept here.
Can anyone provide link for recursion.
答案1
得分: 0
以下是翻译好的内容：
"这个函数没问题，但遗憾的是它访问了树的每个节点。您可以使用if条件来保护递归调用，这些调用肯定会返回0，因为它们的范围（根据BST属性）保证在函数给定的低/高范围之外：
var rangeSumBST = function(root, low, high) {
if (!root) return 0;
let sum = root.val >= low && root.val <= high ? root.val : 0;
if (root.val >= low ) sum += rangeSumBST(root.left, low, high);
if (root.val <= high) sum += rangeSumBST(root.right, low, high);
return sum;
};
如果已知BST不会有重复的值，if条件可以去掉等号条件...所以 root.val > low 和 root.val < high。
我在这里的疑问是，如果每次都给sum=0，它不会被初始化为零。
这里没有问题。请注意，每次调用rangeSumBST都会创建一个具有其自己本地变量的执行上下文。例如，let sum = 0 仅影响该局部变量，而不是同名变量存在于同一函数的其他执行上下文中。
每个调用都负责给定其根的树，并在返回其sum变量的值后，该执行上下文消失--包括该sum变量。然后，调用者信任这个结果对其子树是正确的，并将其累积到自己的sum中。"
英文:
The function is fine, but it is a pity that it visits every node of the tree. You can use if conditions to guard recursive calls which are sure to return 0, because their range (according to the BST property) is guaranteed to be outside the low/high range given to the function:
var rangeSumBST = function(root, low, high) {
if (!root) return 0;
let sum = root.val >= low && root.val <= high ? root.val : 0;
if (root.val >= low ) sum += rangeSumBST(root.left, low, high);
if (root.val <= high) sum += rangeSumBST(root.right, low, high);
return sum;
};
If it is known that the BST will not have duplicate values, the if conditions can drop the equality condition... so root.val > low and root.val < high.
> My doubt here is if we give sum =0 everytime it won't be initialized to zero.
There is no problem there. Be aware that every call of rangeSumBST creates an execution context that has its own local variables. So for example, let sum = 0 will only affect that local variable, and not the variables with the same name that live in other execution contexts of the same function.
Each call is responsible for the tree that it is given the root of, and will return the value of its sum variable to the caller, after which that execution context disappears -- including that sum variable. Then the caller trusts that this result is correct for its child tree, and accumulates it into its own sum.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论