Как мне легко преобразовать итеративное решение в рекурсивное решение?

Question

Я практиковался в вопросе об интервью по преобразованию BST в дважды LinkedList.

Дерево:

станет

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

Ниже приведен мой код:

def treeToDoublyList(self, root):
    """
    :type root: Node
    :rtype: Node
    """

    if not root:
        return

    dummy = Node(-1, None, None)
    prev = dummy
    stack = []
    n = root
    while stack or n:
        while n:
            stack.append(n)
            n = n.left
        n = stack.pop()
        n.left = prev
        prev.right = n
        prev = n
        n = n.right
    dummy.right.left = prev
    prev.right = dummy.right
    return dummy.right

Мне нравится решатьпроблема такого рода итеративно, потому что она очень интуитивно понятна.Но в большинстве случаев меня также попросят реализовать рекурсивное решение.Я знаю, что стек структуры данных похож на поведение рекурсивных функций, но у меня все еще есть трудности с преобразованием итеративной в рекурсивную.Любые советы?

Answer 1

Практически каждая рекурсивная функция может быть построена вокруг "базового случая" и "рекурсивного случая".

• Базовым случаем может быть один узел без дочерних элементов: это дает тривиальный двойной результат-связанный список одного элемента.
• В рекурсивном случае вам нужно построить список для левого дочернего элемента (если есть), затем текущего узла и, наконец, правого дочернего элемента.

Теперь вам нужен способ объединить результаты.Вы можете либо:

• передать (изначально пустой) список в функцию, к которой каждая операция добавляется по порядку, либо
• создать подсписки, которые затем будут объединенывместе в рекурсивном случае.

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

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