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

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

    3

   / \

  9  20

    /  \

   15   7

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

[

  [3],

  [20,9],

  [15,7]

]

package tree;

import java.util.*;

public class ZigzagLevelOrder_103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> line = new ArrayList<>();

        if(root == null)

            return ans;

        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        line.add(root.val);

        ans.add(line);

        line =  new ArrayList<>();

        int size = queue.size();

        int flag = 1;

        while(!queue.isEmpty())

        {

            TreeNode tmp  = queue.poll();

            if(tmp.left!=null)

            {

                queue.add(tmp.left);

                line.add(tmp.left.val);

            }

            if(tmp.right!=null)

            {

                queue.add(tmp.right);

                line.add(tmp.right.val);

            }

            size--;

            if(size==0&&line.size()>0)

            {

                if(flag==1)

                {

                    Collections.reverse(line);

                    flag=0;

                }else

                    flag=1;

                size=queue.size();

                ans.add(line);

                line = new ArrayList<>();

            }

        }

        return ans;

    }

}