資料結構
網路
關係資料庫管理系統 (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
廣告