Java：树的层次遍历模板以及思路分享（JZ59：之字形打印二叉树）

思路：就是层次遍历的变种题目，在层次遍历的基础之上加一个层数的奇偶判断即可！
先来分享一下层次遍历的模板，大家可以多看看，多加练习！

//层次遍历
void levelOrder(Btree T){
    InitQueue(Q);//初始化队列
    Btree p;
    EnQueue(Q, T);//根节点入队
    while(!IsEmpty(Q)){
        DeQueue(Q, p);//节点出队
        visit(p);
        if(p->lchild != null){//节点左子树不为空，则入队
            EnQueue(Q, p->lchild);
        }
        if(p->rchild != null){//节点右子树不为空，则入队
            EnQueue(Q, p->rchild);
        }
    }
} 

层次遍历代码（JZ60）：

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<>>
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();//保存结果
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        if(root==null){ //如果为空，直接返回
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();//对列，先进先出
        queue.offer(root);//根节点入队
        while(!queue.isEmpty()){
            ArrayList<Integer> result1 = new ArrayList<>();//存当前层
            int nowlen = queue.size();//队伍中的节点个数
            for(int i = 0;i<nowlen;i++){
                TreeNode nowroot = queue.poll();//获取队首
                result1.add(nowroot.val);//把当前节点的值插入到result1中
                if(nowroot.left != null){
                    queue.offer(nowroot.left);
                }
                if(nowroot.right != null){
                    queue.offer(nowroot.right);
                }
            }
            result.add(result1);//说明当前层结束，将该层结果加入到result中！
        }
        return result;
    }
}

对于本题而言，我们只需要在最后加入result结果中前加一个判断，使用count变量来记录层数，从第一层开始。代码如下：

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<>>
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();//最终结果
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
          // write code here
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();//Queue是接口，实现类有LinkedList
        queue.offer(root);//根节点入队
        int count = 1;//记录奇偶层 起始为1
        while(!queue.isEmpty()){
            ArrayList<Integer> result1 = new ArrayList<>();//存当前层
            int nowlen = queue.size();//队伍中当前层的节点个数
            for(int i = 0;i<nowlen;i++){
                TreeNode nowroot = queue.poll();//获取队首
                result1.add(nowroot.val);//把当前节点的值插入到result1中
                if(nowroot.left != null){
                    queue.offer(nowroot.left);
                }
                if(nowroot.right != null){
                    queue.offer(nowroot.right);
                }
            }
            //遍历完当前层后，将结果放入result中
            if(count%2 == 1){
                //奇数层
                result.add(result1);
                count++;
            }else{
                Collections.reverse(result1);//反转
                result.add(result1);
                count++;
            }
        }
        return result;
    }
}