剑指offer16 JZ77 按之字形顺序打印二叉树

层次遍历+双端队列（奇偶层逻辑分离）

1、打印奇数层： 队头出队列 在打印 依次添加左节点 在添加右节点；

2、若 deque 为空，说明向下无偶数层，则跳出；

3、打印偶数层： 队尾出队列，在打印，先添加右节点，在添加左节点 ；

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Deque<TreeNode> deque=new LinkedList<>();
        ArrayList res=new ArrayList();
        if (pRoot!=null){
            deque.add(pRoot);
        }
        //层序遍历的遍中国
            while (!deque.isEmpty()){
                ArrayList<Integer> temp =new ArrayList<>();
                //第1层（奇数层）从左向右 添加
                //对头出队  先添加左节点 在右节点
                for(int i = deque.size(); i > 0; i--){
                    TreeNode node=deque.removeFirst();//从头出队
                    temp.add(node.val); //访问节点
                    //将左孩子右孩子加入队列
                    if (node.left!=null){
                        deque.addLast(node.left);
                    }
                    if (node.right!=null){
                        deque.addLast(node.right);
                    }
                  
                }
                res.add(temp);
                //判断是否有下一层  没有下一层提前结束
                 if (deque.isEmpty()){
                    break;
                }
                //第2层 （偶数层）（从右向左）添加
                //先添加左节点 在添加右节点  队尾出队列 逆序
                 temp=new ArrayList<>();
                for (int i = deque.size(); i > 0; i--){
                    TreeNode node=deque.removeLast();//从尾出队
                    temp.add(node.val);
                    if (node.right!=null){
                       deque.addFirst(node.right);
                    }
                    if (node.left!=null){
                        deque.addFirst(node.left);
                    }
                    
                }
                res.add(temp);

            }

            return  res;

    }

}