我在做什么？
我正在做一门关于coursera的课程，这需要我编写一个计算树高的程序。输入是一个父数组，其中每个索引都是节点，其值是节点的父节点。如果节点是根，则其值将为 -1。
到目前为止我做了什么？
我编写了一个算法，通过递归遍历树的子节点直到其根节点并将中间子节点的高度保存在数组(深度变量(中来检查树的高度。由于它是recursion我经常看到一个stackoverflow exception这是很自然的，因为堆栈大小不足以容纳大树。
为了摆脱这个异常，我尝试为我的递归调用找到最佳值，结果接近3100k。此外，当我看到针对一些预定义的测试用例测试我的算法的代码也已将堆栈大小为 1 <<26 传递到线程构造函数中。
我需要知道什么？
有没有更好的方法来解决这个问题？
可以这样增加堆栈大小吗？
这是代码
int computeHeight() {
int[] depth = new int[n];
int maxHeight = 0;
for (int i = 0; i < n; i++) {
int height = computeHeight(parent, depth, i);
maxHeight = Math.max(height, maxHeight);
}
return maxHeight;
}
private int computeHeight(int[] parent, int[] depth, int idx) {
if (parent[idx] == -1) {
// root found
depth[idx] = 1;
return depth[idx];
}
// depth of parent unknown
if (depth[parent[idx]] == 0) {
computeHeight(parent, depth, parent[idx]);
}
depth[idx] = depth[parent[idx]] + 1;
return depth[idx];
}
您遇到堆栈溢出错误似乎很奇怪，我假设这是一个如此简单的问题; 只有当递归是一个非常大的树或由于某种原因在此期间加载大量RAM时，这才往往是递归的问题。我建议你发布你的代码。
至于增加堆栈大小，这不是问题，因为您只是在做练习题。然而，在现实世界中，这可能会带来挑战，并且是使用递归的风险之一。如果您在各种设备上使用应用程序，由于设备的限制，增加堆栈大小可能并不总是可行的。相反，我建议您尽可能避免使用递归，除非您知道要递归的树足够小，不会导致溢出。
如需替代解决方案，请尝试此处。
如果树向右或向左倾斜，例如，如果每个节点只有一个右子节点，那么递归很容易导致堆栈溢出(再次取决于堆栈设置(，不确定其中一个输入是否在您的情况下具有该输入。
这可以通过迭代方式完成：
a( 将所有父项(数组中的值(添加到哈希集中
b(然后遍历所有节点(这里只是从0到n的索引(，看看它是否存在于集合中，如果不是，则为叶子。
c( 然后从叶子遍历到根部以获得高度，同时将高度存储在数组中的每个节点上，以便下次您不必再次爬上相同的路径。
d( 每次更新最大高度。
在现实生活中的工作中，只有当你知道深度限制在一个小值时，你才应该使用递归。
例如，递归测量平衡树是可以的，但递归测量不平衡树则不然。