1. 双端队列+层次遍历

1.1 分析

1. 之字形，要求奇偶层输出顺序相反。
2. 双端队列基于LinkedList实现。奇数层，队头出对，孩子从队尾入队，先左后右。偶数层，队尾出队，孩子从队头入队，先右后左。

1.2 代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Deque;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Deque<TreeNode> dq = new LinkedList<TreeNode>();
        if(pRoot == null) return res;
        dq.offerFirst(pRoot);
        int thisLevel = 1;
        int nextLevel = 0;
        boolean lr = true;//奇偶层标记
        while(!dq.isEmpty()){
            TreeNode node = null;
            if(lr == true){//奇术层，队头出对，孩子从队尾入队，先左后右
              node = dq.pollFirst();
              list.add(node.val);
              thisLevel--;
              //左右孩子入队
                if(node.left!=null){
                    dq.offerLast(node.left);
                    nextLevel++;
                }
                if(node.right!=null){
                    dq.offerLast(node.right);
                    nextLevel++;
                }
            }else{//偶数层，队尾出队，孩子从队头入队，先右后做
                node = dq.pollLast();
                list.add(node.val);
                thisLevel--;
                //左右孩子入队
                if(node.right!=null){
                    dq.offerFirst(node.right);
                    nextLevel++;
                }
                if(node.left!=null){
                    dq.offerFirst(node.left);
                    nextLevel++;
                }
            }//if -else结束
            if(thisLevel == 0){
                thisLevel = nextLevel;
                nextLevel = 0;
                lr = !lr;
                res.add(list);
                list = new ArrayList<>();
            }
        }//结束循环
        return res;
    }
}

1.3 复杂度

空间：O(n)
时间:O(n)