103. 二叉树的锯齿形层序遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //bfs  然后加入一个flag 控制是否将集合反向,  Collections.reverse(list);
            List<List<Integer>> res=new ArrayList();
            Deque<TreeNode> deque=new LinkedList();
            boolean flag=false;
            if(root!=null){
                deque.add(root);
            }
            while(deque.size()>0){
                int n=deque.size();
                List<Integer> list=new ArrayList();
                for(int i=0;i<n;i++){
                    TreeNode node=deque.poll();
                    list.add(node.val);
                    if(node.left!=null){
                        deque.add(node.left);
                    }
                     if(node.right!=null){
                        deque.add(node.right);
                    }
                   
                }
                 if(flag){
                        Collections.reverse(list);
                        
                   }
                    flag=!flag;
                    res.add(list);
            }

            return res;
    }
}