题目：
题解：
1、层序遍历 + 倒序
解题思路：在参考：从上到下打印二叉树II - 轩辕&小站的基础上加入：当是偶数层是将list集合进行反转.
1
if (list.size() % 2 == 1) Collections.reverse(tmp);
复杂度分析：
- 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) 。共完成 少于 N 个节点的倒序操作，占用 O(N)。
- 空间复杂度 O(N) ： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 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 Solution4 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
// 初始化队列
Queue<TreeNode> queue = new LinkedList() {{ add(root); }};
// 初始化返回的list
List<List<Integer>> list = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
// 这样避免了因为queue的值改变，queue.size()变化而报错的情况
// 或者可以这样解决
/*
* int currentLevelSize = queue.size();
* for (int i = 1; i <= currentLevelSize; ++i){...}
* */
for (int i = queue.size(); i > 0; i--) {
TreeNode poll = queue.poll();
tmp.add(poll.val);
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.right != null) {
queue.add(poll.right);
}
}
// 在II的基础上加入当是偶数层是将list集合进行反转
if (list.size() % 2 == 1) Collections.reverse(tmp);
list.add(tmp);
}
return list;
}
}
2、层序遍历 + 双端队列(奇偶层逻辑未分离)
解题思路：
- 利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列）
tmp，并规定：- 奇数层 则添加至
tmp尾部 ， - 偶数层 则添加至
tmp头部 。
- 奇数层 则添加至
- 利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列）
复杂度分析：
- 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) 。共完成 少于 N 个节点的倒序操作，占用 O(N)。
- 空间复杂度 O(N) ： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 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
38
39
40
41
42
43
44// 层序遍历 + 双端队列(奇偶层逻辑未分离)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
// 初始化队列
Queue<TreeNode> queue = new LinkedList() {{
add(root);
}};
// 初始化返回的list
List<List<Integer>> list = new ArrayList<>();
while (!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode poll = queue.poll();
// 奇数层，添加元素至队列尾部
if (list.size() % 2 == 0) {
tmp.addLast(poll.val);
}
// 偶数层，添加元素只队列头部
else {
tmp.addFirst(poll.val);
}
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.right != null) {
queue.add(poll.right);
}
}
list.add(tmp);
}
return list;
}
}
3、层序遍历 + 双端队列（奇偶层逻辑分离）
解题思路：
- 方法一代码简短、容易实现；但需要判断每个节点的所在层奇偶性，即冗余了 N 次判断。
- 通过将奇偶层逻辑拆分，可以消除冗余的判断。
复杂度分析：
- 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) 。共完成 少于 N 个节点的倒序操作，占用 O(N)。
- 空间复杂度 O(N) ： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点同时在
queue或deque中，使用 O(N) 大小的额外空间。
queue实现：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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59// 层序遍历 + 双端队列（奇偶层逻辑分离），使用Queue
class Solution2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
// 初始化队列
Queue<TreeNode> queue = new LinkedList() {{
add(root);
}};
// 初始化返回的list
List<List<Integer>> list = new ArrayList<>();
while (!queue.isEmpty()) {
// 打印奇数层
LinkedList<Integer> tmp = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode poll = queue.poll();
// 每次往尾部加
tmp.addLast(poll.val);
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.right != null) {
queue.add(poll.right);
}
}
list.add(tmp);
if(queue.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode poll = queue.poll();
// 每次往头部加
tmp.addFirst(poll.val);
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.right != null) {
queue.add(poll.right);
}
}
list.add(tmp);
}
return list;
}
}deque实现：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// 层序遍历 + 双端队列（奇偶层逻辑分离），使用Deque
class Solution3 {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) deque.add(root);
while(!deque.isEmpty()) {
// 打印奇数层
List<Integer> tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode node = deque.removeFirst();
tmp.add(node.val);
// 先左后右加入下层节点
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
res.add(tmp);
if(deque.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode node = deque.removeLast();
tmp.add(node.val);
// 先右后左加入下层节点
if(node.right != null) deque.addFirst(node.right);
if(node.left != null) deque.addFirst(node.left);
}
res.add(tmp);
}
return res;
}
}