题解：层序遍历 + 双端队列

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot!=null){
            Deque<TreeNode> q = new LinkedList<>();
            q.add(pRoot);
            boolean leftToRight = true;
            while(!q.isEmpty()){
                int size = q.size();
                ArrayList<Integer> level = new ArrayList<>();
                for(int i=0;i<size;i++){
                    if(leftToRight){
                        TreeNode cur = q.removeFirst();
                        level.add(cur.val);
                        if(cur.left!=null)    q.addLast(cur.left);
                        if(cur.right!=null)    q.addLast(cur.right);
                    }else{
                        TreeNode cur = q.removeLast();
                        level.add(cur.val);
                        if(cur.right!=null)    q.addFirst(cur.right);
                        if(cur.left!=null)    q.addFirst(cur.left);
                    }
                    
                }
                list.add(level);
                leftToRight = !leftToRight;
            }
        }
        return list;
    }

}