Блог

Я был на техническом собеседовании, и один из интервьюеров спросил меня

Какой тип поиска вы бы использовали для сканирования несбалансированного двоичного дерева?

и я не мог ответить, не мог бы кто-нибудь помочь мне с этим ответом для будущих интервью?

Я полагаю, что интервьюер уловил важное различие в том, какие алгоритмы подходят для обхода сбалансированных и несбалансированных деревьев.

Когда известно, что дерево не сбалансировано, становится нецелесообразным пересекать его с помощью рекурсивного DFS, поскольку оно может занимать O(N) места в стеке. Стопки намного меньше кучи, и пространство в стеке слишком ценно, чтобы тратить его таким образом.

По этой причине вы обычно используете BFS или DFS с явным стеком, если хотите пересечь несбалансированное дерево. Вы также можете использовать обход по порядку, опять же с явным стеком, если в дереве нет родительских указателей.

Обратите внимание, что этот вопрос, по-видимому, не имеет никакого смысла, поскольку обход и поиск-это разные вещи, но мой ответ заключается в том, чтобы использовать «поиск» для обхода. Если вы начнете с ответа в уме, вы можете в конечном итоге задать вопрос таким образом.