题目描述

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

来源，leetcode 每日一题 637. 二叉树的层平均值

例如：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

解题思路

层次遍历，使用队列，将每层节点按序加载进来。

代码

/**
* 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> answer;
     queue<TreeNode*> level_node;
     level_node.push(root);
     while(!level_node.empty()) {
         queue<TreeNode*> temp;
         int level_size = level_node.size();
         double level_value = 0;
         while (!level_node.empty()) {
             TreeNode* node = level_node.front();
             level_value += node->val;
             level_node.pop();
             if (node->left != NULL) {
                 temp.push(node->left);
             }
             if (node->right != NULL) {
                 temp.push(node->right);
             }
         }
         answer.push_back(level_value/level_size);
         level_node = temp;
     }
     return answer;
 }
};