#yyds干货盘点# 解决剑指offer：按之字形顺序打印二叉树

1.简述：

描述

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

数据范围：,树上每个节点的val满足 

要求：空间复杂度：，时间复杂度：例如：

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

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

示例1

输入：

{1,2,3,#,#,4,5}

返回值：

[[1],[3,2],[4,5]]

说明：

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

示例2

输入：

{8,6,10,5,7,9,11}

返回值：

[[8],[10,6],[5,7,9,11]]

示例3

输入：

{1,2,3,4,5}

返回值：

[[1],[3,2],[4,5]]

2.代码实现：

import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
TreeNode head = pRoot;
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
if(head == null)
//如果是空，则直接返回空list
return res;
//队列存储，进行层次遍历
Queue<TreeNode> temp = new LinkedList<TreeNode>();
temp.offer(head);
TreeNode p;
boolean flag = true;
while(!temp.isEmpty()){
//记录二叉树的某一行
ArrayList<Integer> row = new ArrayList<Integer>();
int n = temp.size();
//奇数行反转，偶数行不反转
flag = !flag;
//因先进入的是根节点，故每层节点多少，队列大小就是多少
for(int i = 0; i < n; i++){
p = temp.poll();
row.add(p.val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(p.left != null)
temp.offer(p.left);
if(p.right != null)
temp.offer(p.right);
}
//奇数行反转，偶数行不反转
if(flag)
Collections.reverse(row);
res.add(row);
}
return res;
}
}