描述

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

数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 100∣val∣<=100
要求：空间复杂度：O(n)O(n)，时间复杂度：O(n)O(n)

例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是 [[1],[3,2],[4,5]]

思路

自己未想出来，看的代码随想录的二叉树层次遍历写出来的。

1.先将根节点填入队列中，用栈存储其顺序到第三层就会乱。

2.然后将其弹出队列，弹出的同时将其左、右孩子存入到队列中，然后此时队列的长度为当前层元素的个数（此时队列里的元素必然大于等于之前得到的队列长度）。弹出一个元素就将其左、右孩子加入到队列中。

3.遍历的将当前队列中每层的元素弹出，存入到集合中。此时要判断是否是倒序存储了，行数从1开始，奇数行为正序，偶数行为倒序，因此需要一个行数计数器。

4.直到队列为空结束以上操作。

代码

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 {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if(pRoot == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        
        que.add(pRoot);
        int levelNumber = 0;
        while(!que.isEmpty()){
            levelNumber++;
            int length = que.size();
            //存放每层元素的集合
            ArrayList<Integer> item = new ArrayList<>();
            while(length > 0){
                TreeNode cur = que.poll();
                 item.add(cur.val);
                if(cur.left != null){
                    que.add(cur.left);
                }
                if(cur.right != null){
                    que.add(cur.right);
                }
                length--;
            }
            if(levelNumber%2==0){
                    //逆序
                    Collections.reverse(item);
                    resList.add(item);
                }else{
                    //正序
                    resList.add(item);
                }
           
              
        }
        return resList;
    }

}