Как распечатать двоичное дерево уровня по уровню? Интервью вопрос!

Question

Как напечатать уровень двоичного дерева по уровню?

Это вопрос интервью, который я получил сегодня. Конечно же, использование стиля BFS определенно будет работать. Однако следующий вопрос: как распечатать дерево с использованием постоянной памяти? (Таким образом, очередь не может быть использована)

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

Есть предложения?

Спасибо

Answer 1

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

Конечно, это не вся работа, но, вероятно, это самая "хитрая" часть.

Answer 2

Продолжая то, что сказал Джерри Коффин, я ранее задал вопрос о том, чтобы сделать нечто подобное, используя обход по порядку.Он использует ту же логику, что и он.

Проверьте это здесь:

Объясните обход дерева дерева Морриса без использования стеков или рекурсии

Answer 3

Вы можете сделать это, многократно выполняя обход дерева по порядку при печати только тех узлов на указанном уровне. Однако это не является строго постоянной памятью, так как рекурсия использует стек вызовов. И это супер неэффективно. Как O (n * 2 ^ n) или что-то.

printLevel = 1;

while(moreLevels) {

    moreLevels = printLevel(root, 1, printLevel);
    printLevel++;
}

boolean printLevel(Node node, int currentLevel, int printLevel) {

    boolean moreLevels = false;

    if(node == null) {
        return(false);
    }

    else if(currentLevel == printLevel) {
        print the node value;
    }

    else {

        moreLevels |= printLevel(node.leftChild, currentLevel + 1, printLevel);
        moreLevels |= printLevel(node.rightChild, currentLevel + 1, printLevel);
    }

    return(moreLevels);
}