《剑指offer第二版》面试题32 题目三：之字形打印二叉树（j

题目描述

请实现一个函数按照之字形的顺序打印二叉树，即第一行按照从左到右的顺序打印。第二层按照从右到左的顺序，第三层再按照从左往右的方向，以此类推。

解题思路:

1. 定义一个辅助队列queue，一个辅助栈。
2. 先将根节点入队。
3. 得到当前队列的大小n，则n就为当前层的节点数量。
4. 把队列的n个节点依次出队，
   1. 如果当前层为奇数层，则打印出相应节点。
   2. 如果当前层为偶数层，就将节点压入辅助栈，每个节点出队的时候，就将出队的节点的左右节点分别入队。等该层遍历完成后，再将辅助栈出栈，并打印。
   3. n个节点出队后，则该层遍历完成，打印换行符。

代码

void printFormTopToBottom2(TreeNode root){
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    queue.offer(root); // 根节点入队
    int depth = 1;
    while (!queue.isEmpty()) {
        // 打印当前一层的节点
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            // 从队里里拿出一个节点的时候，将这个节点的左右子树分别入队。
            TreeNode tmp = queue.poll();
            if (tmp.left != null) {
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
            }
            if ((depth % 2) == 0) {
                // 偶数层需要从右到左打印，则先用辅助栈存储起来
                stack.push(tmp);
            } else {
                // 奇数层是用左到右打印，正常打印即可
                System.out.print(tmp.value);
            }
        }
        while (!stack.isEmpty()) {
            // 打印偶数层的值
            System.out.print(stack.pop().value);
        }
        System.out.println(); // 换行
        depth ++;
    }
}