数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++实现二叉树每层平均值
假设我们有一个非空的二叉树；我们需要找到每层节点的平均值，并将平均值作为数组返回。
因此，如果输入如下所示：
则输出将为 [3, 14.5, 11]。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 result
定义一个队列 q
将根节点插入 q
当 (q 不为空) 时，执行：
n := q 的大小
定义一个数组 temp
当 n 不为零时，执行：
t := q 的第一个元素
将 t 的值插入 temp
从 q 中删除元素
如果 t 的左子节点不为空，则：
将 t 的左子节点插入 q
如果 t 的右子节点不为空，则：
将 t 的右子节点插入 q
(n 减 1)
如果 temp 的大小为 1，则：
将 temp[0] 插入 result 的末尾
否则，如果 temp 的大小 > 1，则：
sum := 0
对于初始化 i := 0，当 i < temp 的大小时，更新 (i 加 1)，执行：
sum := sum + temp[i]
将 (sum / temp 的大小) 插入 result 的末尾
返回 result
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution{
public:
vector<float> averageOfLevels(TreeNode *root){
vector<float> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
vector<float> temp;
while (n) {
TreeNode* t = q.front();
temp.push_back(t->val);
q.pop();
if (t->left && t->left->val != 0)
q.push(t->left);
if (t->right && t->right->val != 0)
q.push(t->right);
n--;
}
if (temp.size() == 1)
result.push_back(temp[0]);
else if (temp.size() > 1) {
double sum = 0;
for (int i = 0; i < temp.size(); i++) {
sum += temp[i];
}
result.push_back(sum / temp.size());
}
}
return result;
}
};
main(){
Solution ob;
vector<int> v = {3,9,20,NULL,NULL,15,7};
TreeNode *root = make_tree(v);
print_vector(ob.averageOfLevels(root));
}输入
{3,9,20,NULL,NULL,15,7}输出
[3, 14.5, 11, ]
更新于：2020年6月11日
浏览量：127
广告