描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树之字形层序遍历的结果是

代码：

 import java.util.*;

public class Solution {

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
         ArrayList<ArrayList< Integer >> list=new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int level=1;
        
        while(!queue.isEmpty()){
            int count=queue.size(); //当前层的节点个数
            
            ArrayList<Integer> newList=new ArrayList<Integer>();
            for(int i=0;i<count;i++){
                TreeNode newnode=queue.poll();
                if(level%2==0){
                    newList.add(0,newnode.val); //偶数层放到队头
                }else{
                    newList.add(newnode.val);
                }
                
                if(newnode.left !=null){
                    queue.offer(newnode.left);
                }
                if(newnode.right !=null){
                    queue.offer(newnode.right);
                }
            }
            level++;
            list.add(newList);
        }
        return list;
    }
}