637. 二叉树的层平均值
题目链接:637. 二叉树的层平均值(简单)
题目描述
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1:
输入:
3
/ \
9 20
/ \
15 7
输出:[3, 14.5, 11]
解释:
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
提示:
-
节点值的范围在32位有符号整数范围内。
题解
思路:对数进行层次遍历,再求每一层节点的和,除以每一层节点个数即为平均值。
代码(C++):
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int value) : val(value), left(nullptr), right(nullptr) {} }; class Solution { public: vector<double> averageOfLevels(TreeNode* root) { queue<TreeNode*> que; vector<double> result; if (root != nullptr) que.push(root); while (!que.empty()) { int size = que.size(); double sum = 0; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); sum += node->val; if (size - 1 == i) result.push_back(sum/size); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return result; } };
分析:
-
时间复杂度:O(N)
-
空间复杂度:O(N)
-