题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{1,2,3,#,#,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]]思路
按层遍历二叉树，不知道大家了不了解，按层便利就是将每层的元素，按照从左到右的顺序输出。而这道题要求的 之 字形便利，则是第一层是从左到右，下一层则是从右到左。如果之前会写按层遍历，在写这道题会相对简单一点。
以上面这棵树为例：
- 首先咱们通过 队列 这个数据结构来实现每层元素的存储，当遍历到第一层的时候，这时是从左到右的顺序入队列，入了队列之后值存入到集合中。然后再将左节点以及右节点入队。
- 这时到了第二层，这层的顺序是从右到左了，从队列中出队，弹出元素，将上一层所有的元素都弹出后，以相反的顺序存入到集合中。
- 之后重复上面的动作，知道完成便利。
AC代码
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (pRoot == null) {
return result;
}
// 创建一个队列
Queue<TreeNode> queue = new LinkedList<>();
// 根节点先入队
queue.offer(pRoot);
// 当队列不为空时
while (!queue.isEmpty()) {
int size = queue.size();
ArrayList<Integer> list = new ArrayList<>();
// 仅遍历当前层的元素，因为结果是按照层的维度存储的
for (int i = 0; i < size; i ++) {
// 弹出元素
TreeNode node = queue.poll();
list.add(node.val);
// 如果左节点不为空，则入队
if (node.left != null) {
queue.offer(node.left);
}
// 如果右节点不为空，则入队
if (node.right != null) {
queue.offer(node.right);
}
}
// 判断一下是否为奇数层，如果是，则将结果反着存储，
// 这里将根节点那层设定为 第 0 层，为偶数层
if (result.size() % 2 == 1) {
Collections.reverse(list);
}
// 将结果以 层 为维度存储
result.add(list);
}
return result;
} 时间复杂度：O(N), N 为节点数，每个节点都要遍历一次
空间复杂度：o(N), N 为节点数，将这些节点存入到队列中
最后
做这道题之前最后先做一下 层序遍历二叉树，这道题只不过是变了一下而已。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。
网易游戏公司福利 594人发布
