按之字形顺序打印二叉树【Java版】

方法1：使用一个队列（用于层次遍历:所有层），加一个栈（用于高效翻转:偶数层）

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null)return res;
        Stack<Integer> stack = new Stack<Integer>();//stack仅用于偶数层翻转val
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();//queue是奇偶共用
        queue.add(pRoot);
        int layer = 1;//层数用layer (区别于深度depth = layer-1)
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();//新建行
            int size = queue.size();//出本层前记录size，不然难以做到层数的切分  //提前写出来，因为size会变
            for(int i=0; i<=size-1; ++i){
                TreeNode node = queue.get(0);//一定要新建node副本，不然是引用会变
                queue.remove(0);
                if(layer % 2 == 1){
                    list.add(node.val);
                }
                else{//偶数行，需要栈翻转
                    stack.push(node.val);
                }
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
            }
            while(!stack.isEmpty()){
                list.add(stack.pop());//偶数层一次性添加，奇数层一个个添加
            }
            res.add(list);
            ++layer;//本层结束，层数加一
        }
        return res;
    }
}//时间、空间复杂度，都是树的规模 O(N)

方法2：使用一个队列（用于层次遍历），加一个ArrayList（偶行、奇行分别头插、尾插）

import java.util.ArrayList;

public class Solution {//方法2和方法1相比，代码区别仅仅是把stack相关删去，然后换成ArrayList头插法
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null)return res;
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(pRoot);
        int layer = 1;
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = queue.size();
            for(int i=0; i<=size-1; ++i){
                TreeNode node = queue.get(0);
                queue.remove(0);
                if(layer % 2 == 1){
                    list.add(node.val);
                }
                else{
                    list.add(0,node.val);//头插法，逆序 //【代码简洁，但效率比Stack低】
                }
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
            }
            res.add(list);
            ++layer;
        }
        return res;
    }
}//时间、空间都是 O(N)