Правильный вид двоичного дерева без рекурсии

Автор оригинала: Buddha Jyothiprasad.

Проблема Представьте, что у вас есть двоичное дерево и вы хотите получить все узлы, которые будут видны, если смотреть с правой стороны дерева. Как вы печатаете все такие узлы? Конечный результат для этого дерева должен быть 44, 51, 65, 26. Другими словами, первые узлы, которых мы коснемся, если проведем горизонтальные линии с правой стороны дерева. Читайте дальше, чтобы найти решение.

Решение Быстрый совет: всякий раз, когда мы пытаемся что-то сделать без использования рекурсии, вам нужно использовать некоторую вспомогательную структуру данных, такую как очередь или стек. Чтобы решить эту проблему, мы используем очередь.

Чтобы решить эту проблему, мы используем механизм, аналогичный первому обходу по ширине.

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

Если мы сталкиваемся с нулевым узлом, это означает, что мы достигли конца текущего уровня. Нам нужно распечатать узел, снятый с очереди перед этим узлом. Для достижения этой цели мы продолжаем проверять, является ли следующий узел в очереди нулевым узлом, используя метод peek. Как только метод peek вернет значение null, это означает, что это последний узел на текущем уровне, мы должны его распечатать. Если мы получаем нулевой узел, мы должны проверить, есть ли еще узлы, подлежащие удалению из очереди, если узлов больше нет, мы достигли конца двоичного дерева, в противном случае мы только что достигли конца текущего уровня, и в очереди присутствует больше узлов. Найдите программу ниже, написанную на java.

Программа для печати Правого представления Двоичного дерева

public void rightView(Node root) {
    Queue queue = new Queue<>();
    if(root != null) {
        queue.enqueue(root);
        queue.enqueue(null);  // first level is over
    }

    while (!queue.isEmpty()) {
        Node temp = queue.dequeue();
        if(temp == null) {
            if(queue.getSize() > 0)
                queue.enqueue(null);   // current level is over
            continue;
        }

        if(queue.peek() == null)      // next node is null means end of current level, so print it.
            System.out.println(temp.data);
        if(temp.left != null)
            queue.enqueue(temp.left);
        if(temp.right != null)
            queue.enqueue(temp.right);
    }
}

Что вы думаете об этом решении? Можете ли вы придумать более простое решение? Дайте мне знать в комментариях.

Оригинал: “https://www.codementor.io/@buddha/right-view-of-binary-tree-without-recursion-h0en0ql5s”