二叉树:最小值和最大值之间所有节点的总和 [英] Binary Tree: summation of all nodes between a min and max value

问题描述

我有一个分配给我的随机生成的BST的根目录.为此任务，我得到了随机生成的测试用例.

I have an assignment where I am given the root of a randomly generated BST. I am given randomly generated test cases for this assignment.

作业说明如下:

为您提供了二叉搜索树的根节点T和两个整数:最小值和最大值请注意，最小值和最大值不一定存储在树.确定存储在T中的所有大于或等于的键的总和等于最小值，并且小于或等于最大值.实施算法递归

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

}

我的问题是，如果在递归过程中的任何时候，该节点触发基本情况，并导致我的功能无法正常完成自身.我相信可能要归咎于我的订购.

my issue is that if at any point during my recursion, the node trips the base case and causes my function to not complete itself properly. I believe that my ordering may be to blame.

分类的节点定义为:

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

    public int key;

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

推荐答案

以这种方式思考:当您到达不在所需范围内的节点时，算法将停止.如果根本身超出范围会怎样?您将立即返回0.您需要修正退出条件，以便在到达 null 时，递归仅停止 ，因为您不知道在[min，max]出现在您当前所在节点的子树中.然后，在递归本身中，您应该确定是否将当前节点添加到总和中.

Think about it this way: the moment you reach a node which isn't in the desired range, your algorithm stops. What happens if the root itself is out of range? You'll just return 0 right off the bat. You need to fix your exit condition so that your recursion stops only when you've reached a null, since you can't know how many nodes that are within range of [min, max] are present in the sub-tree of the node you're currently in. Then, in the recursion itself, you should make the decision whether to add the current node to the overall sum or not.

可能的实现-可能会破坏先行，我建议您仅在自己解决问题后再看:

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]的期望范围内，则会将其添加到计算中.

Explanation: each recursive call sums up the results of the left and right subtrees. The key of the node you're currently in is added to the calculation iff it is within the desired range of [min, max].

这篇关于二叉树:最小值和最大值之间所有节点的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！