使用深度樹的高度

Question

嗨全部 我需要一些方向來計算函數高度的時間複雜度，它使用函數深度來獲取樹的高度。

因此函數是這樣的：

height(Tree) 
height h = 0; 
for(each external node of T) 
h = max(height, getdepth(external node)); 

時，每個節點都在同一水平該算法的最壞的情況會是什麼？ 在這種情況下，我們最終會爲所有外部節點做同樣的事情，因爲所有節點將具有相同的高度 - n *（n-some_i）= n^2？ 但是用這種方式思考 - 當樹左右兩側不平衡時，複雜度將再次爲1 + 2 + 3 + 4 ... + n = n^2？

我有點困惑。這是關於這個想法的正確方法嗎？

感謝

Answer 1

你會更好，從根開始，做樹的遞歸遍歷，跟蹤當前的深度和看作是你走的最大深度。這樣你只需要遍歷一次樹。如果分別計算每個節點的深度，則最終遍歷樹N次，其中N是外部節點的數量。