返回二叉树范围内节点数

huangapple go评论74阅读模式
英文:

Returning the number of nodes within a range in a binary tree

问题

我正在尝试编写一个方法,该方法返回二叉树中数值在某个范围内的节点数量。

以下是您请求的完整代码的翻译部分:

public class StaffInfo {

    final String name;
    final int monthHired;

    public StaffInfo(String name, int monthHired){
        this.name = name;
        this.monthHired = monthHired;
    }
}

public class StaffTree implements Iterable<StaffInfo>{
    public StaffNode root;

    public StaffTree(StaffInfo c) {
        this.root = new StaffNode(c);
    }

    private StaffTree(StaffNode c) {
        this.root = c;
    }
}

class StaffNode {

    StaffInfo data;
    StaffNode senior;
    StaffNode same;
    StaffNode junior;

    public StaffNode(StaffInfo data) {
        this.data = data;
        this.senior = null;
        this.same = null;
        this.junior = null;
    }
}

public int numInRange(int monthMin, int monthMax) {

    int count = 0;

    if (monthMin > monthMax) {
        return 0;
    }

    if (root.data.monthHired >= monthMin && root.data.monthHired <= monthMax) {
        count++;
    }

    if (root.senior != null) {
        root.senior.numInRange(monthMin, monthMax);
    }
    if (root.same != null) {
        root.same.numInRange(monthMin, monthMax);
    }
    if (root.junior != null) {
        root.junior.numInRange(monthMin, monthMax);
    }
    return count;
}

请注意,您提供的代码中可能存在问题,可能会导致StackOverflowError。如果您需要进一步的帮助,请提供更多信息。

英文:

I am trying to code a method that returns the number of nodes in a binary tree who have a value between a range.

Here if the full code as requested:

public class StaffInfo {
final String name;
final int monthHired;
public StaffInfo(String name, int monthHired){
this.name = name;
this.monthHired = monthHired;
}
public class StaffTree implements Iterable&lt;StaffInfo&gt;{
public StaffNode root;
public StaffTree(StaffInfo c) {
this.root = new StaffInfo(c);
}
private StaffTree(StaffNode c) {
this.root = c;
}
class StaffNode {
StaffInfo data;
StaffNode senior;
StaffNode same;
StaffNode junior;
public StaffNode(StaffInfo data) {
this.data = data;
this.senior = null;
this.same = null;
this.junior = null;
}

Here is the code for the method I have trouble with:

public int numInRange(int monthMin, int monthMax) {

            int count = 0;

            if (monthMin &gt; monthMax) {
                return 0;
            }

            if (root.data.monthHired &gt;= monthMin &amp;&amp; root.data.monthHired &lt;= monthMax) {
                count++;
            }

            if (root.senior != null) {
                root.senior.numInRange(monthMin, monthMax);
            }
            if (root.same != null) {
                root.same.numInRange(monthMin, monthMax);
            }
            if (root.junior != null) {
                root.junior.numInRange(monthMin, monthMax);
            }
            return count;

I am mimicking an office thus each node can have a child that's a senior, junior, or same (determined by the hiring date). monthMin and monthMax are both integers representing the number of months since January 2015.

When I run the code above, I get a StackOverFlowError.

Any help is appreciated!

If the problem is unclear, please let me know in the comments and I will edit it right away.

答案1

得分: 1

你使用了全局变量 root,所以每当 root 调用它的子节点时,会无限次发生。您需要在函数中将子节点作为 root 传递。然后您可以进行计数。

public int numInRange(Root root, int monthMin, int monthMax) {

    int count = 0;

    if (monthMin > monthMax) {
        return 0;
    }

    if (root.data.monthHired >= monthMin && root.data.monthHired <= monthMax) {
        count++;
    }

    if (root.senior != null) {
        count += numInRange(root.senior, monthMin, monthMax);
    }
    if (root.same != null) {
        count += numInRange(root.same, monthMin, monthMax);
    }
    if (root.junior != null) {
        count += numInRange(root.junior, monthMin, monthMax);
    }
    return count;
}

尝试使用这个版本。

英文:

You used root as global variable thats why every time root call his child. it will be happens infinite time. You need to pass child as root in function. then u can count.

public int numInRange(Root root, int monthMin, int monthMax) {
int count = 0;
if (monthMin &gt; monthMax) {
return 0;
}
if (root.data.monthHired &gt;= monthMin &amp;&amp; root.data.monthHired &lt;= monthMax) {
count++;
}
if (root.senior != null) {
root.senior.numInRange(root.senior,monthMin, monthMax);
}
if (root.same != null) {
root.same.numInRange(root.same,monthMin, monthMax);
}
if (root.junior != null) {
root.junior.numInRange(root.junior,monthMin, monthMax);
}
return count;
}

Try with this.

huangapple
  • 本文由 发表于 2020年4月6日 17:12:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/61056433.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定