Какова временная сложность обхода дерева, я уверен, что это должно быть очевидно, но мой плохой мозг не может это исправить прямо сейчас.
Какова временная сложность обхода дерева?
Ответ 1
Это зависит от того, какой тип обхода вы выполняете и алгоритм, но обычно это будет O (n), где n - общее количество узлов в дереве. Каноническая рекурсивная реализация первого обхода глубины будет потреблять память (в стеке) в порядке самого глубокого уровня, который на сбалансированном дереве будет log (n).
Ответ 2
Разве это не было бы просто для дерева с n узлами?
Вы посещаете каждый древо-отпуск один раз, не так ли? Поэтому я бы сказал, что он линейный.