二叉树的层序遍历力扣c
时间: 2023-10-30 13:00:47 浏览: 57
二叉树的层序遍历是一种广度优先搜索的算法,它按照层次逐层地遍历二叉树的节点。可以通过使用一个队列来实现层序遍历。首先将根节点入队,然后循环执行以下步骤,直到队列为空:
1. 弹出队首节点,并将其值加入结果数组。
2. 如果该节点有左孩子,则将左孩子入队。
3. 如果该节点有右孩子,则将右孩子入队。
4. 重复以上步骤直到队列为空。
以下是一个用C++实现的二叉树层序遍历的示例代码:
```cpp
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> result; // 存放每层的平均值
queue<TreeNode*> q; // 队列
if (root == nullptr) {
return result;
}
q.push(root); // 根节点入队
while (!q.empty()) {
double sum = 0; // 当前层节点值的和
int size = q.size(); // 当前层节点数量
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(sum / size); // 计算平均值并加入结果数组
}
return result;
}
};
```
以上代码通过遍历每一层的节点,并计算该层节点值的和和数量,然后将平均值加入结果数组。最终返回结果数组即可。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [力扣刷题之二叉树的层序遍历](https://blog.csdn.net/m0_58367586/article/details/124107118)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT0_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]