本文主要是介绍【C++】637二叉树的层平均值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
#include <iostream>
#include <queue>
#include <vector>using namespace std;// 二叉树节点的结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};vector<double> averageOfLevels(TreeNode* root) {vector<double> averages;if (root == nullptr) return averages;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();double sum = 0;for (int i = 0; i < size; ++i) {TreeNode* current = q.front();q.pop();sum += current->val;if (current->left != nullptr) q.push(current->left);if (current->right != nullptr) q.push(current->right);}averages.push_back(sum / size);}return averages;
}int main() {// 创建二叉树TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);// 计算每一层的平均值vector<double> result = averageOfLevels(root);// 输出结果cout << "每一层节点的平均值为: ";for (double val : result) {cout << val << " ";}cout << endl;return 0;
}使用广度优先搜索BFS遍历二叉树的每一层，并计算每一层节点的平均值
时间复杂度分析：
遍历每个节点： 在最坏情况下，我们需要访问二叉树中的每个节点一次。因此，遍历所有节点的时间复杂度为 O(N)，其中 N 是二叉树中的节点数。
每个节点访问的操作： 在每个节点处，我们需要执行一些常数时间的操作，例如将节点值相加和将其左右子节点入队。这些操作的时间复杂度是 O(1)。
因此，总体时间复杂度为 O(N)。
空间复杂度分析：
队列空间： 我们使用了一个队列来进行广度优先搜索。在最坏情况下，队列可能包含二叉树中的所有叶子节点，即二叉树的最后一层节点。因此，队列的空间复杂度为 O(N)。
结果数组空间： 我们需要一个数组来存储每一层节点的平均值。在最坏情况下，这个数组将包含二叉树的所有层级的平均值。因此，结果数组的空间复杂度也是 O(N)。
综合考虑队列空间和结果数组空间，总体空间复杂度为 O(N)。
这篇关于【C++】637二叉树的层平均值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
