本文主要是介绍637. Average of Levels in Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
637. 二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:3/ \9 20/ \15 7 输出: [3, 14.5, 11] 解释: 第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].注意：
- 节点值的范围在32位有符号整数范围内。
解法一
//时间复杂度O(n), 空间复杂度O(n)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> q1;q1.push(root);while(!q1.empty()) {queue<TreeNode*> q2;q2.swap(q1);long sum = 0, n = 0;while(!q2.empty()) {TreeNode* temp = q2.front();q2.pop();sum += temp->val;n++;if(temp->left) q1.push(temp->left);if(temp->right) q1.push(temp->right);}res.push_back((double)sum / n);}return res;}
};层序遍历。为了区分层次，使用两个队列。q1记录上一层结点，每次循环把q1给q2，清空q1，遍历q2时把其个数及和记录，q2空时说明当前层遍历结束，开始下一层。
2019/06/13 20:45
这篇关于637. Average of Levels in Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
