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

问题描述

我有一个任务，我得到了一个随机生成的 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;
    }
}

标签： javabinary-treebinary-search-tree

这样想：当你到达一个不在所需范围内的节点时，你的算法就会停止。如果根本身超出范围会发生什么？您将立即返回 0。您需要修复退出条件，以便递归仅在达到 a 时停止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] 的所需范围内。

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

问题描述

解决方案

推荐阅读