题目主要信息

1、给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

2、要求：空间复杂度：O*(n)，时间复杂度：O*(n)

方法一：使用队列

具体方法

1. 当树的根节点为空，则直接返回空列表 [] 打印结果空列表 result ，包含根节点的双端队列 deque ；

2. 层次遍历： 当 queue 为空时跳出；

3. 新建列表 result1，用于临时存储当前层打印结果；

4. 当前层打印循环： 循环次数为当前层节点数（即 queue 长度）；

5. 出队： 队首元素出队，记为 node；

6. 打印： 若为奇数层，将 node.val 添加至result1 尾部；否则，添加至result1头部；

7. 添加子节点： 若 node 的左（右）子节点不为空，则加入 deque ；

8. 将当前层结果result1 并添加入 res ；

9. 返回值： 返回打印结果列表 result 即可；

Java代码

import java.util.*;

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

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

    }

}
*/
public class Solution {
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();//保存所有的结果
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        //思路：就是层次遍历
        if(pRoot == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        int count = 1;//记录奇偶层 起始为1
        queue.offer(pRoot);//入队
        while(!queue.isEmpty()){
            int length = queue.size();
            ArrayList<Integer> result1 = new ArrayList<>();
            //遍历当前队列，如果有元素就出来，放入到result1中，如果这个元素的左右子树都有，那就放入队中
            for(int i=0;i<length;i++){
                TreeNode curTree = queue.poll();//队首出队
                if(curTree.left!=null){//左子树入队
                    queue.offer(curTree.left);
                }
                if(curTree.right!=null){
                    queue.offer(curTree.right);
                }
                result1.add(curTree.val);
            }
            //增加一个判断
            //遍历完当前层后，将结果放入result中
            if(count%2 == 1){
                //奇数层
                result.add(result1);
                count++;
            }else{
                Collections.reverse(result1);//反转
                result.add(result1);
                count++;
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度 ：$O(n)O(n)$ $nn$ 为二叉树的节点数量，即 BFS 需循环n次
• 空间复杂度 ：$O(n)O(n)$ 最差情况下，即当树为满二叉树时，最多有$n\mathrm{/}2n/2$个树节点 同时 在 queue 中，使用 $O(n)O(n)$ 大小的额外空间。

方法二：双栈

具体方法

可以用栈来保存奇偶层结果，然后在遍历栈，将结果存入到result中。

• 在奇数层的时候，由于是顺序打印，而栈是先进后出，所以需要先存右节点，后存左节点，出栈的时候就左-右
• 在偶数层的时候，由于是逆序打印，而栈是先进后出，所以需要先存左节点，后存右节点，出栈的时候就是右左

Java代码

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) {
            return result;
        }
        // 存放奇数层的节点
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(pRoot);
        // 存放偶数层的节点
        Stack<TreeNode> stack2 = new Stack<>();
        // 表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
        int level = 1; 
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            // 处理奇数层
            if(level % 2 != 0) {
                ArrayList<Integer> list = new ArrayList<>();
                // 奇数层按顺序
                while(!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    if(node != null) {
                        // 收集打印结果
                        list.add(node.val);
                        // stack2保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印，满足题目要求
                        stack2.push(node.left);
                        stack2.push(node.right);
                    }
                }
                // 收集当前层的结果
                if(!list.isEmpty()) {
                    result.add(list);
                    level++;
                }                 
            } else {
                // 处理偶数层
                ArrayList<Integer> list = new ArrayList<>();        
                while(!stack2.isEmpty()) {
                    TreeNode node = stack2.pop();
                    if(node != null) {
                        list.add(node.val);
                        // 需要按顺序push，因为stack1是用在奇数层按顺序输出结果的
                        stack1.add(node.right);
                        stack1.add(node.left);
                    }
                }
                if(!list.isEmpty()) {
                    result.add(list);
                    level++;
                }
            }
        }        
        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)，遍历树的每个节点
• 空间复杂度：O(n)，两个临时栈