题目描述：

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

思考：其实和上一题差不多，只是需要掌握一些API，使用起来方便

1）分层打印，且每层输出顺序不同！这三道题层层递进！

2）这道题想到的思路是：不同的层添加左右节点的顺序不同；并且是输出按照 先进先出FIFO；添加下一行节点时，要从后往前进行添加，LIFO

知识点：

1) 双端队列，就是队列的两端都可以添加！java中 LinkedList就是双端队列

2) LinkedList中的 addFirst 将元素每次都添加到链表的头部;add和addLast每次按顺序将元素添加到链表的尾部

2）removelast：每次移除的都是链表最后的元素！

手写垃圾代码：

class Solution {

    //本题的关键问题就是：判断每一行是从左还是从右输出
    public List<List<Integer>> levelOrder(TreeNode root) {
    
        if(root == null) return new ArrayList<>();

        int k = 0;//判断是第几层
        Queue<TreeNode> queue = new LinkedList<>();//用来进行节点的存储，借助FIFO的特性，记录顺序
        List<List<Integer>> res = new ArrayList<>();//最后输出的结果
        queue.add(root);//将根节点加入，开始进行循环

        //两个while交替进入
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            //每次队列存的是一行节点
            if((k % 2) == 0){
                for(int i = queue.size();i > 0;i--){
                    TreeNode node = queue.poll();//要输出的节点
                    list.add(node.val);//这里是节点数值输出的操作
                    stack.add(node);
                }
                while(!stack.isEmpty()){
                    if(stack.peek().right != null) queue.add(stack.peek().right);
                    if(stack.peek().left != null) queue.add(stack.peek().left);
                    stack.pop();
                }
            }else if((k % 2) == 1){
                for(int i = queue.size();i > 0;i--){
                    TreeNode node = queue.poll();//要输出的节点
                    list.add(node.val);//这里是节点数值输出的操作
                    stack.add(node);
                }
                while(!stack.isEmpty()){
                    if(stack.peek().left != null) queue.add(stack.peek().left);
                    if(stack.peek().right != null) queue.add(stack.peek().right);
                    stack.pop();
                }
            }
            res.add(list);
            k = k + 1;
        }
        return res;
    }
}

答案代码：对自己代码的优化：判断层自己用的整数k作为标记；答案用链表长度判断

作者：jyd
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
来源：力扣（LeetCode）

1）层序遍历＋双端队列 LinkedList

class Solution {

    //本题的关键问题就是：判断每一行是从左还是从右输出
    public List<List<Integer>> levelOrder(TreeNode root) {
        //1.分层遍历 + 双向队列
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            //拿一个双向链表，进行节点记录的队列照常进行
            //用双向链表进行 数据反转
            //上一题中的链表为ArrayList 单向链表
            LinkedList<Integer> temp = new LinkedList<>();
            //for(int i = 0;i < queue.size();i++){//这样queue的size每次都换，不对
            for(int i = queue.size();i > 0;i--){//队列还在不断增加，但是只输出最开始的长度，也就是一层
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) temp.add(node.val);//偶数页还是从左往右
                else if(res.size() % 2 == 1) temp.addFirst(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

2) 相比于15题，只需要将偶数页的值反转以下就行 Collections.reverse(List list)

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            for(int i = queue.size();i > 0;i--){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            //说明下一页要加进去的是偶数页，需要倒序
            if(res.size() % 2 == 1) Collections.reverse(temp);
            res.add(temp);
        }
        return res;
    }
}