我在做什么 ？我正在 coursera 上開設一門課程，該課程要求我編寫一個計算樹高的程序。輸入是一個父數組，其中每個索引都是節點，其值是節點的父節點。如果節點是根節點，它的值將為 -1。到目前為止我做了什么？我編寫了一個算法，通過遞歸遍歷其子節點直到其根節點并將中間子節點的高度保存在數組（深度變量）中來檢查樹的高度。為了擺脫這個異常，我嘗試為我的遞歸調用找到最佳值，結果它接近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];}
3 回答
躍然一笑
TA貢獻1826條經驗 獲得超6個贊
如果樹向右或向左傾斜，例如如果每個節點只有一個右子節點，那么遞歸很容易導致計算器溢出（再次取決于堆棧設置），不確定輸入之一是否具有您的情況。
這可以以迭代方式完成：
a) 將所有父項（數組中的值）添加到 HashSet
b) 然后遍歷所有節點（這里只是從 0 到 n 的索引），看看它是否存在于集合中，如果不存在，它就是一片葉子。
c) 然后從葉子遍歷到根來獲取高度，同時將每個節點的高度存儲在數組中，這樣下次您就不必再次爬上相同的路徑。
d) 每次更新最大高度。
MMMHUHU
TA貢獻1834條經驗 獲得超8個贊
您遇到堆棧溢出錯誤似乎很奇怪，我假設這是一個如此簡單的問題；當它是一棵非常大的樹或者您出于某種原因在它期間加載大量 RAM 時，這只會成為遞歸的問題。我建議你發布你的代碼。
至于增加堆棧大小，這不是問題，因為您只是在做練習題。然而，在現實世界中，這可能會帶來挑戰，并且是使用遞歸的風險之一。如果您在各種設備上使用您的應用程序，由于設備的限制，增加堆棧大小可能并不總是可行的。相反，我建議您盡可能避免使用遞歸，除非您知道要遞歸的樹足夠小而不會導致溢出。
添加回答
舉報
0/150
提交
取消