java - OutOfMemoryError递归创建树？

 root = new TreeNode(N);
 constructTree(N, root);

 private void constructTree(int N, TreeNode node) {
    if (N > 0) {
        node.setLeft(new TreeNode(N-1));
        constructTree(N-1, node.getLeft());
    }
    if (N > 1) {
        node.setMiddle(new TreeNode(N-2));
        constructTree(N-2, node.getMiddle());
    }
    if (N > 2) {
        node.setRight(new TreeNode(N-3));
        constructTree(N-3, node.getRight());
    }

假设N是根号，则三个将创建N-1，N-2，N-3的左中右节点。

例如：

     5
   / | \
  4  3  2
 /|\
3 2 1

等等

我的TreeNode类具有以下变量：

private int number;
private TreeNode left, middle, right;

每当我构造一个大于28的整数的树时，都会收到OutOfMemoryError。我的递归方法效率极低还是自然吗？谢谢！

最佳答案

理论上，深度为N的完整三叉树将具有(3^(N+1) - 1) / 2个节点。如果N为28，则表示34,315,188,682,441个节点。如果每个节点以某种方式仅占用了1个字节，那仍然是31.2 TB的RAM。在此之前，您将耗尽内存。

编辑：但是，您的代码似乎没有生成完整的树。当我运行以下程序以计算新节点的数量时：

static long nodes = 0;

static void constructTree(int N) {
   if (N > 0) {
       ++nodes;
       constructTree(N-1);
   }
   if (N > 1) {
       ++nodes;
       constructTree(N-2);
   }
   if (N > 2) {
       ++nodes;
       constructTree(N-3);
   }
}

public static final void main (String[] args) throws Exception {
    nodes = 1;
    constructTree(28);
    System.out.println(nodes);
}

假设您的TreeNode构造函数未创建新节点，则表明您正在N = 28处创建34,850,335个新节点，在N = 29处创建64,099,760个新节点。考虑到您暗示N = 28成功，这更有意义。由于您没有显示TreeNode，所以我们无法确切知道它将使用多少内存，但是这些数字与典型的JVM内存限制处于同一数量级。您可以稍微增加您的最大JVM内存，以挤出一个或两个以上的级别。

但是，您可能希望仔细考虑为什么要生成此树，并尝试提出一种不同的算法来执行自己的工作。