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

Question

这是一个面试问题。
我们想按级别打印二叉树，但进行一些更改:
在偶数级别，打印将从左到右。
在奇数级别，打印将从右到左。

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

我尝试使用代码here (正常的层级顺序遍历，方法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