题解 | #二叉树的之字形层序遍历#

思路：和广度优先搜索一样的思路，只是每隔一层需要将元素倒置，这里只需使用ArrayList的头插法即可。

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        if(root==null ) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();   //返回result，存储每层节点
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);    //放入根节点

        int level=1;  //定义层数，根节点为第一层
        while(!queue.isEmpty()){
            ArrayList<Integer> arr=new ArrayList<>();     //放置每一层节点的动态数组，每次循环将被重置

            //计数每层的节点，进行循环放入ArrayList数组中
            int levelNum=queue.size();  
            for(int i=0;i<levelNum;i++){
                TreeNode node=queue.poll();

                //判断是奇数层还是偶数层，偶数层需要使用头插法
                if(level%2!=0){
                arr.add(node.val);
                }else{
                    arr.add(0,node.val);
                }
                //加入节点的左右子树
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }
            result.add(arr);
            level++;    //一层增加一
        }    
        return result;
    }
}