-
Notifications
You must be signed in to change notification settings - Fork 14k
/
LeetCode第102号问题：二叉树的层序遍历.md
99 lines (65 loc) · 2.12 KB
/
LeetCode第102号问题：二叉树的层序遍历.md
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# LeetCode 第 102 号问题：二叉树的层序遍历
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
>
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
题目来源于 LeetCode 上第 102 号问题：二叉树的层序遍历。题目难度为 Medium，目前通过率为 55.8% 。
### 题目描述
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: `[3,9,20,null,null,15,7]`,
```
3
/ \
9 20
/ \
15 7
```
返回其层次遍历结果：
```
[
[3],
[9,20],
[15,7]
]
```
### 题目解析
该问题需要用到**队列**
- 建立一个queue
- 先把根节点放进去，这时候找根节点的左右两个子节点
- 去掉根节点，此时queue里的元素就是下一层的所有节点
- 用for循环遍历，将结果存到一个一维向量里
- 遍历完之后再把这个一维向量存到二维向量里
- 以此类推，可以完成层序遍历
### 动画描述
### 代码实现
```
/// BFS
/// Time Complexity: O(n), where n is the number of nodes in the tree
/// Space Complexity: O(n)
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
queue<pair<TreeNode*,int>> q;
q.push(make_pair(root, 0));
while(!q.empty()){
TreeNode* node = q.front().first;
int level = q.front().second;
q.pop();
if(level == res.size())
res.push_back(vector<int>());
assert( level < res.size() );
res[level].push_back(node->val);
if(node->left)
q.push(make_pair(node->left, level + 1 ));
if(node->right)
q.push(make_pair(node->right, level + 1 ));
}
return res;
}
};
```
