二叉树：最小值和最大值之间所有节点的总和

Question

我有一个作业，其中给出了随机生成的 BST 的根。我得到了这个作业的随机生成的测试用例。

作业说明如下：

You are given the root node of a binary search tree, T, and two integers: min, and max. Note that min and max are not necessarily stored in the tree. Determine the sum of all keys stored in T that are larger than or equal to min, and smaller than or equal to max. Implement your algorithm recursively

不允许我拥有全局变量或创建辅助函数

我当前的代码是这样的：

private static int problem2(Node root, int min, int max){

 if(root = null){
    return 0;
 }

 if(root.key < min || root.key > max){     
   int lft = problem2(root.left, min, max);
   int rgt = problem2(root.right, min, max);
   int sum = lft + rgt;
   return sum;
 }

}

我的问题是，如果在我的递归过程中的任何时候，节点都会触发基本情况并导致我的函数无法正确完成自身。我相信我的订单可能是罪魁祸首。

节点分类定义为：

private static class Node
{
    public Node left = null;
    public Node right = null;

    public int key;

    public Node(int key)
    {
        this.key = key;
    }
}

Answer 1

这样想：当你到达一个不在所需范围内的节点时，你的算法就会停止。如果根本身超出范围会怎样？你马上就会 return 0 。您需要修复退出条件，以便当您达到 null 时递归停止仅，因为您不知道在 [ min, max]存在于你当前所在节点的子树中。然后，在递归本身中，你应该决定是否将当前节点添加到总和中。

可能的实现 - 前面有剧透，我建议你自己解决后再看：

private static int problem2(Node root, int min, int max){

 if(root == null){
    return 0;
 }

 int sum = 0;
 // No point in keeping the recursion right/left if the current key is
 // larger/smaller than the desired range - usage of BST property:
 if (root.key <= max) {
    sum += problem2(root.right, min, max);
 }
 if (root.key >= min) {
    sum += problem2(root.left, min, max);
 }
 // If root is within range add it to sum:
 if (root.key <= max && root.key >= min){
    return root.key + sum;
 } else {
    return sum;
 }

}

解释：每次递归调用对左右子树的结果求和。如果您当前所在的节点的密钥在 [min, max].

的所需范围内，则会将其添加到计算中

Answer 2

我认为问题出在这里：

if(root == null || root.key < min || root.key > max){
    return 0;
 }

想象一下这种情况1：min:10, max:20, root.key:8，这里直接return 0，但是有可能这个根的右边child有一些节点可能在可接受的范围。

同样， case1 : min:10, max:20, root.key:22, 这里直接return 0, 但有可能这个根的左边child 有一些节点可能在可接受的范围内.

您需要修改您的代码，如果 root.key < min，则查找右边的节点 child，而如果 root.key > max，则在根的左侧 child 寻找节点。

此外，您代码中的 if 条件相同，因此您的流程永远不会进入第二个 if 块的定义。

Answer 3

由于这显然是一项用于教育目的的作业，我不会 post 一个完整的解决方案，但我会给出可能有用的提示：

基本上你做对了，方法定义很好。

然而，该方法本身存在一些错误：

首先，这段代码：

if(root == null || root.key < min || root.key > max){
    return 0;
}

第一个条件是你已经走到尽头的情况，ok。但是剩下的呢？某个节点小于 'min.' 的事实是否意味着其所有 "children" 也将无法 "contribute" 总和并且必然是 "out of range"？

免责声明：我在这里依赖于它是一个二叉树的事实（如问题标题中所写），所以我不假设元素的任何顺序。即使它是 Binary Search Tree 我的评论仍然有效（想想为什么）。

现在，递归本身：

if(root.key < min || root.key > max){     
   int lft = problem2(root.left, min, max);
   int rgt = problem2(root.right, min, max);
   int sum = lft + rgt;
   return sum;
 }

你这里说的基本上是"if my current root's key is out of [min,max] range then enter the recursion"。相反，你应该说 "if my current root's key is within the [min,max] range then enter the recursion"

请注意，由于我的第一条评论，此代码也可能会发生变化 - 请注意边角情况

二叉树：最小值和最大值之间所有节点的总和

Binary Tree: summation of all nodes between a min and max value

java

binary-tree

binary-search-tree