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 内存,以再挤出一到两个级别。
但是,您可能希望准确地思考为什么要生成这棵树,并尝试提出一种不同的算法来完成您正在做的事情。
关于java - 递归创建树时出现 OutOfMemoryError 错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19761221/