树的层序遍历
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
思路：
此题与上一题类似，唯一的区别在于每一层需要变更一次打印的顺序。由于层序遍历限制了我们必须用队列来完成，容易想到可以方便从两端访问的数据结构就是双端队列 Deque。
那么只要用一个标志记录当前层的遍历方向（从左往右，或是从右往左），即可完成题目的要求。这个标志可以是一个二元变量，每一层切换一次，也可以用当前层数的奇偶性直接判断。
时间复杂度：O(n)
空间复杂度：O(n)
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new LinkedList<>();
Deque<TreeNode> q = new LinkedList<>();
if(root != null) {
q.offerLast(root);
}
int flag = 0;
while (!q.isEmpty()) {
List<Integer> l = new LinkedList<>();
for (int i = q.size(); i > 0; i--) {
if (flag == 0) {
TreeNode cur = q.pollFirst();
l.add(cur.val);
if (cur.left != null) {
q.offerLast(cur.left);
}
if (cur.right != null) {
q.offerLast(cur.right);
}
} else {
TreeNode cur = q.pollLast();
l.add(cur.val);
if (cur.right != null) {
q.offerFirst(cur.right);
}
if (cur.left != null) {
q.offerFirst(cur.left);
}
}
}
flag = 1 - flag;
ret.add(l);
}
return ret;
}
}
|
