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

Question

我有一个任务，在这个任务中，我得到了一个随机生成的BST的根。我得到了这个任务的随机生成的测试用例。

这个任务的描述如下。

给你一个二进制搜索树的根节点T 和两个整数：min和max。注意，min和max不一定存储在树中。确定T中存储的所有大于或等于min、小于或等于max的键的总和。递归地实现你的算法

我不允许使用全局变量或创建辅助函数。

我目前的代码是这样的。

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

这样想：当你到达一个不在期望范围内的节点时，你的算法就会停止。如果根本身不在范围内，会发生什么？你就会马上返回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，这里会直接返回0，但有可能在这个根的右子节点上有一些节点可能在接受范围内。

同理，case1 : min:10, max:20, root.key:22这里会直接返回0，但也有可能在这个根的左子节点上有一些节点在接受范围内。

你需要修改你的代码，使if root.key < min，则寻找右侧子节点，如果 root.key > max，然后寻找根的左子上的节点。

另外，无论是 if 的条件是一样的，因此你的流程永远不会进入第二个定义的 if 块。

Answer 3

由于这显然是一个以教育为目的的作业，我不会发布完整的解决方案，不过我会给出一些可能会有帮助的提示。

基本上你做的都是对的，方法的定义也很好

但是方法本身有几个错误。

首先是这段代码

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

第一个条件是针对你已经到达终点的情况，好的，但是其他的呢？某一个节点小于'min.'，是否意味着它的所有 "子节点 "也无法为和 "做贡献"，一定会 "超出范围"？

免责声明：我在这里依靠的事实是，它是一个二进制树（如问题的标题所写），所以我不假设任何元素的顺序。即使它是一棵 二进制搜索树 我的意见还是有道理的（想想为什么）。

现在，递归本身。

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;
 }

你在这里说的基本上是 "如果我的当前根的密钥超出了[min,max]范围，那么就进入递归". 而你应该说 "如果我的当前根的密钥是 在[最小，最大]范围内 然后输入递归"

请注意，由于我的第一条评论，这段代码也可能会发生变化--只是要注意角落里的情况。