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

Question

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

分配说明如下：

您将得到二叉搜索树的根节点T和两个整数：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

由于它显然是出于教育目的的任务，因此我不会发布完整的解决方案，但是我会给出可能会有所帮助的提示：

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

然而，该方法本身存在几个错误：

首先，这段代码:

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]范围之外，那么进入递归”。相反，你应该说“如果我当前根的键在[min，max]范围内，那么进入递归”

请注意，由于我的第一个评论，此代码也可能会发生变化-只要留意角落情况

Answer 2

我认为问题在于:

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

想象一下这种情况1：min：10，max：20，root.key：8，在这里这将直接返回0，但该根的右子节点上可能存在一些可能在可接受的范围内。

类似地，案例1：min： 10， max： 20，root.key:22，这里这将直接返回0，但可能在该根的左子节点上有一些节点可能在可接受的范围内。

您需要以这样的方式修改代码：如果＜code＞root.key

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

Answer 3

这样想:当你到达一个不在期望范围内的节点时，你的算法停止。如果根本身超出范围会怎么样？你会立刻返回0。您需要修正您的退出条件，以便您的递归只在到达< code>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] 范围内。