Как найти высоту бинарного дерева не используя узлы (на массивах)?
Я делал на узлах, но по времени не проходит.
int height(struct Node *root){
if (root == NULL){
return 0;
}
return 1 + max(height(root -> left), height(root -> right));
}
Ответы (2 шт):
Автор решения: Librake
→ Ссылка
В классической реализации на массиве подразумевается, что дерево уже сбалансировано. В таком случае его высота log(n)
Автор решения: Mikhailo
→ Ссылка
Судя по "не проходит по времени" у вас какая-то олимпиадная задача. В таком случае довавьте поле "высота узла" в узел, и при вставке/удалении узла обновляйте необходимые поля. Обновление в сбалансированном дереве займет то же O(log N), что и вставка, так что ничего во времени вы не теряете, зато высоту дерева получаете за O(1).