打印二叉树的层序遍历，从左到右和从右到左交替

Question

这是一道面试题。
我们想按层次打印二叉树，但有一些变化：
在偶数层，打印将从左到右。
在奇数级别，打印将从右到左。

示例：以下树的输出将为 1 3 2 4 7:

我尝试使用代码 here（正常级别顺序遍历，方法 2），只是保持级别的一些变化（为了知道是从左到右还是从右到左打印）当然，还要添加相关条件以便在正确的方向上打印。

不幸的是，我下面的代码在不小的树上效果不佳 - 我无法理解如何在循环中以正确的顺序存储节点。请告诉我如何解决它：

辅助class：

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

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

主要class：

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

我认为按部就班地完成任务应该更容易，即

正在处理当前关卡
正在按正确的顺序准备下一关。

在这种情况下，您不需要 LevelNode class 来存储级别，因为在处理级别时级别是已知的。

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

打印二叉树的层序遍历，从左到右和从右到左交替

Print level order traversal of binary tree, from left to right and right to left alternately

java

tree

binary-tree

tree-traversal