Skip to content

Commit e0c5815

Browse files
committed
Create 103.二叉树的锯齿形层次遍历(中等).md
1 parent 8c2d62e commit e0c5815

1 file changed

Lines changed: 75 additions & 0 deletions

File tree

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
```text
2+
题目: 给定一个二叉树,返回其节点值的锯齿形层次遍历;
3+
(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)
4+
1.BFS(广度优先遍历):
5+
[1]思路: 从左到右遍历添加,再从右到左遍历添加,再从左到右遍历添加,以此类推
6+
(1)使用双端队列保存每层的节点,在最后添加一个null,作为该层遍历完的标识;
7+
(2)原本是要更改节点放到队列中的位置,来实现从左到右再从右到左,但遍历每个节点时都要考虑其两子节点的位置太麻烦了
8+
(3)简化: 控制<添加当前节点的左右子节点>的位置 -> 控制<添加节点值>的位置
9+
(4)使用一个布尔变量保存遍历的方向,当遍历到null时,说明该层结束就需要变更方向
10+
[2]实现:
11+
class Solution {
12+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
13+
// 对节点进行判空
14+
if (root == null) {
15+
return new ArrayList<>();
16+
}
17+
// 定义一个结果集合
18+
List<List<Integer>> results = new ArrayList<>();
19+
// 定义一个LinkedList做双端队列用来保存节点(节点的添加依旧是从左到右)
20+
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
21+
// 向栈中添加初始节点(根节点与null)
22+
nodeQueue.addLast(root);
23+
// null用来表示当前层遍历结束(该层遍历结束后可做一些操作,如添加遍历结果到最终结果集,更改遍历方向等)
24+
nodeQueue.addLast(null);
25+
// 定义一个变量保存遍历方向(初始方向是从左到右即正向)
26+
boolean isLtoR = true;
27+
// 定义一个LinkedList用来保存每一层的值
28+
LinkedList<Integer> levelList = new LinkedList<>();
29+
// 遍历树
30+
while (nodeQueue.size() > 0) {
31+
// 从双端队列中吐出头部节点
32+
TreeNode curr = nodeQueue.pollFirst();
33+
if (curr != null) {
34+
if (isLtoR) {
35+
// 当前层是正向则添加到尾部(右边)
36+
levelList.addLast(curr.val);
37+
} else {
38+
// 当前层是反向则添加到头部(左边)
39+
levelList.addFirst(curr.val);
40+
}
41+
// 将当前节点的不为null的子节点添加到节点集合
42+
if (curr.left != null) {
43+
nodeQueue.addLast(curr.left);
44+
}
45+
if (curr.right != null) {
46+
nodeQueue.addLast(curr.right);
47+
}
48+
} else {
49+
// 进入此处说明该层已遍历结束,需要做的处理有:
50+
// 保存该层结果到结果集、添加下一层的结束标志、更改遍历方向
51+
results.add(levelList);
52+
levelList = new LinkedList<>();
53+
if (nodeQueue.size() > 0) {
54+
nodeQueue.addLast(null);
55+
}
56+
isLtoR = !isLtoR;
57+
}
58+
}
59+
return results;
60+
}
61+
}
62+
class TreeNode {
63+
int val;
64+
TreeNode left;
65+
TreeNode right;
66+
TreeNode(int x) {
67+
val = x;
68+
}
69+
}
70+
[3]复杂度分析:
71+
(1)时间复杂度: O(N),其中N是树中节点的数量,每个节点仅访问一次,双端队列的插入操作为常数时间,即最后为O(N)
72+
(2)空间复杂度: O(N),其中N是树中节点的数量
73+
除了输出数组,主要的内存开销是双端队列,任何时刻,队列中最多只存储两层节点;因此其大小不超过2L(L是一层的最大节点数);
74+
包含最多节点的层可能是完全二叉树的叶节点层,大约有L=N/2个节点,因此最坏情况下,空间复杂度为2*N/2=N;
75+
```

0 commit comments

Comments
 (0)