题解 | #按之字形顺序打印二叉树#

import java.util.*;
import java.util.ArrayList;

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

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Stack<Integer> s=new Stack<Integer>();
        Queue<TreeNode> q_l=new ArrayDeque<TreeNode>();//上一层的队列
         Queue<TreeNode> q_n=new ArrayDeque<TreeNode>();//下一层的队列
        ArrayList<Integer> arr1=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer> > arr2=new ArrayList<ArrayList<Integer> >();
       
        boolean flag_ceng=false;
        if(pRoot==null)
            return arr2;
         q_l.offer(pRoot);//添加头节点
        while(true)
        {
            pRoot=q_l.poll();//弹出队列元素
            arr1.add(pRoot.val);
            if(pRoot.left!=null)
                q_n.offer(pRoot.left);//添加左节点
            if(pRoot.right!=null)
                q_n.offer(pRoot.right);//添加左节点
            
            if(q_l.isEmpty()==true)//上一次的队列弹出完成
            {
                if(flag_ceng)//当为偶数层，反转
                    Collections.reverse(arr1);
                arr2.add(arr1);
                if(q_n.isEmpty()==true)//当此次循环也无填充时
                    break;
                q_l=q_n;//将上一层用下一层替换
                flag_ceng=!flag_ceng;
                q_n=new ArrayDeque<TreeNode>();//清空下一层队列，用于后续填充
                arr1=new ArrayList<Integer>();
                
                //arr1.clear();//清空每一层arr
            }
        }
        return arr2;
    }


}