Вывести порядок следования уровней двоичного дерева слева направо и справа налево поочередно

Question

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

Пример: вывод для следующего дерева будет 1 3 2 4 7:

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

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

вспомогательный класс:

public class Node {
    int data; 
    Node left, right; 

    public Node(int item) { 
        data = item; 
        left = null; 
        right = null; 
    } 
}                 

Основной класс:

public class BinaryTree {

    class LevelNode {
        int level;
        Node node;

        public LevelNode(int level, Node node) {
            this.level = level;
            this.node = node;
        }
    };

    private Node root; 

    void printLevelOrder(){ 
        int level = 0;
        Queue<LevelNode> queue = new LinkedList<LevelNode>();

        queue.add(new LevelNode(level, root)); 
        while (!queue.isEmpty()){ 

            LevelNode tempNode = queue.poll();
            level = tempNode.level;
            System.out.print(tempNode.node.data + " "); 

            if ( (level & 1) == 1 ) {
                if (tempNode.node.left != null) { 
                    queue.add(new LevelNode(level + 1, tempNode.node.left)); 
                } 
                if (tempNode.node.right != null) { 
                    queue.add(new LevelNode(level + 1, tempNode.node.right));
                }
            }
            else {
                if (tempNode.node.right != null) { 
                    queue.add(new LevelNode(level + 1, tempNode.node.right));
                }
                if (tempNode.node.left != null) { 
                    queue.add(new LevelNode(level + 1, tempNode.node.left)); 
                } 
            }
        } 
    }
 }                

И для примера выше, мой код печатает: 1 3 2 7 4
Вот основной метод, который генерирует вывод:

public static void main (String[] args) {
   BinaryTree tree_level = new BinaryTree(); 
   tree_level.root = new Node(1); 
   tree_level.root.left = new Node(2); 
   tree_level.root.right = new Node(3); 
   tree_level.root.left.left = new Node(4); 
   tree_level.root.right.right = new Node(7); 
   tree_level.printLevelOrder(); 
}

Answer 1

По моему мнению, должно быть легче выполнить задачу шаг за шагом, то есть

1. Обработка текущего уровня
2. Подготовка следующего уровня в правильном порядке.

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

void printLevelOrderFixed() {
    List<Node> currLevel = new ArrayList<>();
    currLevel.add(root);

    int level = 1;
    while(currLevel.size() > 0) {

        // Output
        currLevel.forEach(x -> System.out.print(x + " "));

        // Preparation for next level
        List<Node> nextLevel = new ArrayList<>();
        for (int i = currLevel.size() - 1; i >= 0; i--) {
            Node left = currLevel.get(i).left;
            Node right = currLevel.get(i).right;

            if (level % 2 == 0) {
                if (left != null) nextLevel.add(left);
                if (right != null) nextLevel.add(right);                    
            } else {
                if (right != null) nextLevel.add(right);    
                if (left != null) nextLevel.add(left);
            }
        }
        currLevel.clear();
        currLevel.addAll(nextLevel);

        level++;
    }
    System.out.println("");
}

Расширенный тест драйвера с вашим результатом и фиксированным результатом:

public static void main(String[] args) {
    System.out.println("Example 1. Expected output: 1 3 2 4 7 ");

    BinaryTree tree_level = new BinaryTree();
    tree_level.root = new Node(1);
    tree_level.root.left = new Node(2);
    tree_level.root.right = new Node(3);
    tree_level.root.left.left = new Node(4);
    tree_level.root.right.right = new Node(7);

    tree_level.printLevelOrder();
    System.out.println();
    tree_level.printLevelOrderFixed();
    System.out.println();

    System.out.println("Example 2. Expected output: 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ");
    /*             1
     *         3       2
     *       4   5   6   7
     *      5 4 3 2 1 0 9 8
     *     6               7
     *    9                 8
     */
    BinaryTree tree_level2 = new BinaryTree();
    tree_level2.root = new Node(1);

    tree_level2.root.left = new Node(3);
    tree_level2.root.right = new Node(2);

    tree_level2.root.left.left = new Node(4);
    tree_level2.root.left.right = new Node(5);
    tree_level2.root.right.left = new Node(6);
    tree_level2.root.right.right = new Node(7);

    tree_level2.root.left.left.left = new Node(5);
    tree_level2.root.left.left.right = new Node(4);
    tree_level2.root.left.right.left = new Node(3);
    tree_level2.root.left.right.right = new Node(2);
    tree_level2.root.right.left.left = new Node(1);
    tree_level2.root.right.left.right = new Node(0);
    tree_level2.root.right.right.left = new Node(9);
    tree_level2.root.right.right.right = new Node(8);

    tree_level2.root.left.left.left.left = new Node(6);
    tree_level2.root.right.right.right.right = new Node(7);
    tree_level2.root.left.left.left.left.left = new Node(9);
    tree_level2.root.right.right.right.right.right = new Node(8);

    tree_level2.printLevelOrder();
    System.out.println();
    tree_level2.printLevelOrderFixed();
    System.out.println();
}

Выход тестового драйвера:

Example 1. Expected output: 1 3 2 4 7 
1 3 2 7 4 
1 3 2 4 7 

Example 2. Expected output: 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 
1 2 3 6 7 4 5 0 1 8 9 4 5 2 3 7 6 8 9 
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9