使用深度树的高度

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是外部节点的数量。