题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0≤n≤1500,树上每个节点的val满足∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

示例

image.png

输入：{1,2,3,#,#,4,5}
输出： [[1],[3,2],[4,5]]
说明：如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

思路

这其实就是一个升级版的层序遍历.
观察其特点,无非就是奇数层和偶数层的输出顺序不一样. 这样就有了初步的解题思路,设置标识符flag(可以为整数型,也可以为boolean类型,整数类型无非就是对奇偶数的判断).
其余的思路就是层序遍历的思路,在每遍历新的一层之前,改变flag的值!flag(这里以boolean类型为例),然后就是利用Collections.reverse(list)对链表进行翻转.
详情可看代码

这里,小编再提一下我初次遇到这道题的思路,前面的几乎一样,就是在实现链表反转这里,小编不熟悉Java库,没想到还有Colection.reverse这个方法可以用.
所以,小编在想反转的时候首先就想到了咱们的栈,也就是根据flag的值判断,从队列出来的值是否需要进一次栈实现反转

代码实现

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) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        TreeNode head = pRoot;
        if(head==null){
            return res;
        }
        Queue<TreeNode> temp = new LinkedList<TreeNode>();
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while(!temp.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = temp.size();
            flag = !flag;
            for(int i=0;i<size;++i){
                p = temp.poll();
                if(p.left!=null){
                    temp.offer(p.left);
                }
                if(p.right!=null){
                    temp.offer(p.right);
                }
                list.add(p.val);
            }
            if(flag){
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }
}