На ваш вопрос - "какой подход будет оптимальным для интервьюера" - на самом деле не может ответить никто, кроме самого интервьюера. Однако различия между возможными подходами к этой проблеме заслуживают обсуждения.
Для начала отметим, что итеративный, и рекурсивный подходы используют стек; итеративный подход имеет явный стек, но рекурсивная функция работает с использованием стека вызовов, который не управляется программистом. Следовательно, вспомогательное пространство, используемое при любом подходе, будет асимптотически одним и тем же, но с более низкой константой для итеративного подхода, поскольку он помещает в стек только узлы, а рекурсивный подход помещает все кадры вызовов, включая все локальные переменные.
Обратите внимание, что вспомогательное пространство равно O(h), где h — высота дерева, а не O(n), где n — количество узлов. Это важно, поскольку наихудший случай будет зависеть от того, является ли дерево сбалансированным. Для несбалансированного дерева высота h равна O(n) в худшем случае, тогда как для сбалансированного дерева h равна O(log н). В вопросе не указывается, что дерево сбалансировано, поэтому существует риск того, что рекурсивный подход переполнит stack, когда высота дерева слишком велика. Напротив, итеративный подход сохраняет явный стек в основной памяти.
Это все обсуждение эффективности, но в программировании есть нечто большее, чем алгоритмическая эффективность. Например, если дерево никогда не будет очень большим, вы можете предпочесть рекурсивный подход, так как его намного проще писать; требуется всего несколько строк очень чистого кода. Императивный подход требует создания стека, а также извлечения и извлечения из него в цикле, поэтому код, вероятно, будет длиннее и труднее для понимания. Не стоит недооценивать ценность чистого, легкого для понимания кода.
Другое дело, что вы перешли сразу к обходу по порядку как к решению проблемы, но если задача состоит в том, чтобы подсчитать количество узлов в двоичном дереве, то вы можете проходить его в любом порядке. Обход в предварительном порядке немного проще реализовать итеративно, чем обход в порядке, и он столь же эффективен.
В качестве альтернативы, если сама структура данных может быть изменена, то легко дать каждому узлу свойство, содержащее кардинальность его поддерева. Операции вставки, удаления и повторной балансировки должны быть изменены, чтобы сохранить это свойство, но дополнительная работа составляет O (1), и это позволяет вычислить размер дерева за O (1), просто читая кардинальность корневого узла. свойство. Добавление этого свойства имеет и другие преимущества, такие как поддержка операции «найти k-й узел» за время O(h) вместо O(h) > + k).
person
kaya3
schedule
13.11.2019
