CC BY 4.0(除特别声明或转载文章外)
📝题目
给定一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
📝思路
想法一:递归遍历。难点大概就是如何加入新的一层。
想法二:BFS(广度优先搜索)。利用队列先进先出的特性逐层存储、读取和弹出子节点。
🐣:都是上学期数据结构的内容,有点遗忘了…
📝题解
//想法一
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;
}
//想法二
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;
}