返回二叉树范围内节点数

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

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

问题

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

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

  1. public class StaffInfo {
  3.     final String name;
  4.     final int monthHired;
  6.     public StaffInfo(String name, int monthHired){
  7.         this.name = name;
  8.         this.monthHired = monthHired;
  9.     }
  10. }
  12. public class StaffTree implements Iterable<StaffInfo>{
  13.     public StaffNode root;
  15.     public StaffTree(StaffInfo c) {
  16.         this.root = new StaffNode(c);
  17.     }
  19.     private StaffTree(StaffNode c) {
  20.         this.root = c;
  21.     }
  22. }
  24. class StaffNode {
  26.     StaffInfo data;
  27.     StaffNode senior;
  28.     StaffNode same;
  29.     StaffNode junior;
  31.     public StaffNode(StaffInfo data) {
  32.         this.data = data;
  33.         this.senior = null;
  34.         this.same = null;
  35.         this.junior = null;
  36.     }
  37. }
  39. public int numInRange(int monthMin, int monthMax) {
  41.     int count = 0;
  43.     if (monthMin > monthMax) {
  44.         return 0;
  45.     }
  47.     if (root.data.monthHired >= monthMin && root.data.monthHired <= monthMax) {
  48.         count++;
  49.     }
  51.     if (root.senior != null) {
  52.         root.senior.numInRange(monthMin, monthMax);
  53.     }
  54.     if (root.same != null) {
  55.         root.same.numInRange(monthMin, monthMax);
  56.     }
  57.     if (root.junior != null) {
  58.         root.junior.numInRange(monthMin, monthMax);
  59.     }
  60.     return count;
  61. }

请注意，您提供的代码中可能存在问题，可能会导致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:

  1. public class StaffInfo {
  2. final String name;
  3. final int monthHired;
  4. public StaffInfo(String name, int monthHired){
  5. this.name = name;
  6. this.monthHired = monthHired;
  7. }
  8. public class StaffTree implements Iterable&lt;StaffInfo&gt;{
  9. public StaffNode root;
  10. public StaffTree(StaffInfo c) {
  11. this.root = new StaffInfo(c);
  12. }
  13. private StaffTree(StaffNode c) {
  14. this.root = c;
  15. }
  16. class StaffNode {
  17. StaffInfo data;
  18. StaffNode senior;
  19. StaffNode same;
  20. StaffNode junior;
  21. public StaffNode(StaffInfo data) {
  22. this.data = data;
  23. this.senior = null;
  24. this.same = null;
  25. this.junior = null;
  26. }

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

  1. public int numInRange(int monthMin, int monthMax) {
  3.             int count = 0;
  5.             if (monthMin &gt; monthMax) {
  6.                 return 0;
  7.             }
  9.             if (root.data.monthHired &gt;= monthMin &amp;&amp; root.data.monthHired &lt;= monthMax) {
  10.                 count++;
  11.             }
  13.             if (root.senior != null) {
  14.                 root.senior.numInRange(monthMin, monthMax);
  15.             }
  16.             if (root.same != null) {
  17.                 root.same.numInRange(monthMin, monthMax);
  18.             }
  19.             if (root.junior != null) {
  20.                 root.junior.numInRange(monthMin, monthMax);
  21.             }
  22.             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 传递。然后您可以进行计数。

  1. public int numInRange(Root root, int monthMin, int monthMax) {
  3.     int count = 0;
  5.     if (monthMin > monthMax) {
  6.         return 0;
  7.     }
  9.     if (root.data.monthHired >= monthMin && root.data.monthHired <= monthMax) {
  10.         count++;
  11.     }
  13.     if (root.senior != null) {
  14.         count += numInRange(root.senior, monthMin, monthMax);
  15.     }
  16.     if (root.same != null) {
  17.         count += numInRange(root.same, monthMin, monthMax);
  18.     }
  19.     if (root.junior != null) {
  20.         count += numInRange(root.junior, monthMin, monthMax);
  21.     }
  22.     return count;
  23. }

尝试使用这个版本。

英文:

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.

  1. public int numInRange(Root root, int monthMin, int monthMax) {
  2. int count = 0;
  3. if (monthMin &gt; monthMax) {
  4. return 0;
  5. }
  6. if (root.data.monthHired &gt;= monthMin &amp;&amp; root.data.monthHired &lt;= monthMax) {
  7. count++;
  8. }
  9. if (root.senior != null) {
  10. root.senior.numInRange(root.senior,monthMin, monthMax);
  11. }
  12. if (root.same != null) {
  13. root.same.numInRange(root.same,monthMin, monthMax);
  14. }
  15. if (root.junior != null) {
  16. root.junior.numInRange(root.junior,monthMin, monthMax);
  17. }
  18. return count;
  19. }

Try with this.

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

发表评论

匿名网友

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

确定