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

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {

         ArrayList<Integer> arr=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer> > arr1=new  ArrayList<ArrayList<Integer> >();
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        Stack<Integer> s=new Stack<Integer>();
        if(pRoot==null) return arr1;
        q.offer(pRoot);
        TreeNode tail=pRoot,last=pRoot;
        int flag=0;
        while(!q.isEmpty())
        {
            TreeNode temp=q.poll();
            
            if(flag%2==0)
            {
               arr.add(temp.val);
            }
            else
            {
                s.push(temp.val);
            }
          
               
           
            if(temp.left!=null)
            {
                q.offer(temp.left);
                tail=temp.left;
            }
            if(temp.right!=null)
            {
                q.offer(temp.right);
                tail=temp.right;
            }
            
              //一层结束时
            if(temp.val==last.val) 
            {
                 last=tail;
                if(flag%2==0)
                {
                    arr1.add(new ArrayList<Integer>(arr));
                    arr.clear();
                    flag++;
                    
                }
                else{
                    while(!s.isEmpty())
                    {
                        arr.add(s.pop());
                    }
                    arr1.add(new ArrayList<Integer>(arr));
                    arr.clear();
                    flag++;
                }
            }
        }
         return arr1;
    }
   

}