📝题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 给定一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
|
📝思路
想法一：递归遍历。难点大概就是如何加入新的一层。
想法二：BFS（广度优先搜索）。利用队列先进先出的特性逐层存储、读取和弹出子节点。
🐣：都是上学期数据结构的内容，有点遗忘了…
📝题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void traverse(vector<vector<int>>& result, int depth, TreeNode* root){
if (root == NULL) return;
if (depth >= result.size())
result.push_back(vector<int> {});
result[depth].push_back(root->val);
traverse(result, depth+1, root->left);
traverse(result, depth+1, root->right);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
traverse(result, 0, root);
return result;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
vector<vector<int>> levelOrder(TreeNode* root){
queue<TreeNode*> q;
vector<vector<int>> result;
if (root != NULL)
q.push(root);
while(!q.empty()){
int count = q.size();
vector<int> layer;
while(count > 0){
TreeNode* tmp = q.front();
q.pop();
layer.push_back(tmp->val);
if (tmp->left != NULL) q.push(tmp->left);
if (tmp->right != NULL) q.push(tmp->right);
count --;
}
result.push_back(layer);
}
return result;
}
|
