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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        if(root==null){return new ArrayList<>();}
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        LinkedList<TreeNode> q=new LinkedList<>();
        q.offer(root);
        //设置level初始值为1，与实际层数向对应。二叉树的顶层是第一层
        int level=1;
        while(!q.isEmpty()){
            ArrayList<Integer> tempList=new ArrayList<>();
            int len=q.size();
            for(int i=0;i<len;i++){

                TreeNode cur;
                //每一层都是先进行出队列操作，在出队的同时将其子节点入队，得到下一次层节点的队列
                //偶数层，right先入队列，队首节点出列，right加入到队尾位置
                if(level%2==0){
                    cur=q.poll();
                    if(cur.right!=null){q.offer(cur.right);}
                    if(cur.left!=null){q.offer(cur.left);}
                }else{
                    //奇数层，left先入队列，队尾节点出列，left加入到队首位置
                    cur=q.pollLast();
                    if(cur.left!=null){q.offerFirst(cur.left);}
                    if(cur.right!=null){q.offerFirst(cur.right);} 
                }
                tempList.add(cur.val);
            }
            level++;
            res.add(tempList);
       }
        return res;
    }
}

主要是找到奇数层和偶数层入队列和出队列的规律。