public class Node {

  int value;
  List<Node> childNodes;

  Node(int x) {
      value = x;
      childNodes = new ArrayList<>();
  }
}


这是节点的定义。

 public static double averageNodes(Node root) {
      int numofnodes = 0;
      int sum = 0;
      Stack<Node> s = new Stack<Node>();
      s.add(root);
      while (!s.isEmpty()) {
          Node n = s.pop();
          numofnodes++;
          sum += n.value;
            for (Node temp : root.childNodes) {
              s.push(temp);  // Line 1
          }
      }
      return sum / numofnodes;
  }


我使用深度优先搜索和堆栈遍历树。但是,当我单击“在eclipse中运行”时,在第1行中显示了一条错误消息“线程“ main”中的异常java.lang.OutOfMemoryError:Java堆空间”。有人知道要修复该代码以避免此错误吗?

最佳答案

您不必总是添加root节点的子代,而必须添加n节点的子代:

for (Node temp : n.childNodes) {
    s.push(temp);  // Line 1
}


您的代码会导致无限循环和无限增长的堆栈,因为您总是一遍又一遍地添加root节点的子代。

您将一个元素取出,将所有子元素放入,取出,将它们全部放入,依此类推。这只是一个小错误,但其造成的后果却非常严重。

09-27 09:57