脚本宝典收集整理的这篇文章主要介绍了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; } };
分析:
@R_358_1304@:O(N)
空间复杂度:O(N)
以上是脚本宝典为你收集整理的637. 二叉树的层平均值全部内容,希望文章能够帮你解决637. 二叉树的层平均值所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。