Высота дерева по глубине

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 - количество внешних узлов.