题目

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 分析
  这是二叉树的层序遍历的变形。

• 层序遍历
  主要思路：利用队列
  S1：如果root节点不为空，那么让root节点 入队
  S2：从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
  S3：循环，直到队列为空。
  有如下代码

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //1. 首先对于不为空的结点，先把该结点加入到队列中
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }

        while (!queue.isEmpty()) {
            //2.从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return null;
    }

有了层序遍历就好办了。在上述代码基础是上只要做如下修改
修改1：只有在每一层的所有元素都遍历后，创建一个小的list，存放当前层的数据
修改2：交替反转 当前层的数据。

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> bigList=new ArrayList<>();
         //1. 首先对于不为空的结点，先把该结点加入到队列中
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
        }else{
            return bigList;
        }

        boolean flag=false;
        while(!queue.isEmpty()){

            List<Integer> smallList=new ArrayList<>();
            //修改1:当前层元素变量完成后，才会创建新的小list
            int size = queue.size();
            while(size!=0){
                TreeNode poll = queue.poll();

                smallList.add(poll.val);
            	//2.从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
                if(poll.left!=null){
                    queue.offer(poll.left);
                }
                if(poll.right!=null){
                    queue.offer(poll.right);
                }
                size--;
            }

			//修改2：交替反转
            flag=!flag;
            if(flag==false){
                Collections.reverse(smallList);
            }

            bigList.add(smallList);
        }
        return bigList;
    }