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

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

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]

1. 锯齿形层序遍历和层次遍历的区别在于，在每一层访问当前节点并且把孩子节点放入下一次访问的队列当中时，先放入的孩子在下一层的访问中最后才被访问，实际上让你实现的就是一个分层(分组)访问的栈。一开始的想法是用两个栈来实现，一个栈用来保存并访问当前层的节点，另一个栈用来保存当前层节点的孩子节点；但是提交了发现莫名其妙的超时了。
2. 后面换了一种方式用链表，设置三个指针，beg标记当前访问节点，end标记当前层最后访问的一个节点，nend标记下一层最后访问的节点，beg走到end表示当前层走完开始进入下一层。有两个需要注意的点:

• beg的孩子节点插入链表需要用头插法(先进后出)。
• 每层遍历中nend节点更新为当前层往链表后插入的第一个孩子节点。

当然也可以用容器LinkedList,直接用封装的size()方法来标记当前层有几个节点，不过add()方法默认尾插法，因此访问每一层时需要调整顺序(或者使用add(int index,E element)头插)。

 			while(!queue.isEmpty()) // LinkedList<TreeNode> queue=new LinkedList<>();
            {
                List<Integer> path=new ArrayList<>();
                int size=queue.size();
                for(int i=size-1;i>=0;i--)
                {
                    TreeNode node=queue.get(i);
                    path.add(node.val);
                    if(right==1)
                    {                       
                        if(node.left!=null)
                        queue.add(node.left);
                        if(node.right!=null)
                        queue.add(node.right);
                    }
                    else
                    {                       
                        if(node.right!=null)
                        queue.add(node.right);
                        if(node.left!=null)
                        queue.add(node.left);
                    }
                    queue.remove(i);
                }
                res.add(path);
                right=0-right;
            }