之字形打印二叉树

分析：考察数据结构二叉树，考察的算法是 bfs。bfs 的核心就是用队列实现，
主要常见的几种题型：
1 什么要求都没有，只要求层序遍历（只要一个队列实现）
2 要求按层打印（两个队列）
3 要求之字形打印（两个队列）
4 要求倒序打印，，，各种姿势打印。。

不外乎就是要记住每一层，只要理解了层序遍历本质：先进先出，队列空一层就结束了。各种题型就是手到擒来了。
整个程序的可读性很强，就不写注释了。。。。

public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
    // write code here
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    if(root==null){
        return res;
    }
    bfs(root,res);
    return res;
}

public void bfs(TreeNode root,ArrayList<ArrayList<Integer>> res){
    ArrayList<Integer> list=new ArrayList<>();
    LinkedList<TreeNode> l1=new LinkedList<>();
    LinkedList<TreeNode> l2=new LinkedList<>();
    if(root!=null){
        l1.add(root);
    }
    while(!l1.isEmpty() || !l2.isEmpty()){
        while(!l1.isEmpty()){
            TreeNode node=l1.removeFirst();
            list.add(node.val);
            if(node.left!=null){
                l2.add(node.left);
            }
            if(node.right!=null){
                l2.add(node.right);
            }
        }
        if(!list.isEmpty()){
            res.add(new ArrayList<>(list));
            list.clear();
        }
        while(!l2.isEmpty()){
            TreeNode node=l2.removeFirst();
            list.add(node.val);
            if(node.left!=null){
                l1.add(node.left);
            }
            if(node.right!=null){
                l1.add(node.right);
            }
        }
        if(!list.isEmpty()){
            Collections.reverse(list);
            res.add(new ArrayList<>(list));
            list.clear();
        }
    }
}