[Leetcode]637. Average of Levels in Binary Tree

链接：LeetCode636

给一个非空二叉树，返回每层的平均值组成的数组。

相关标签：树
解法：BFS迭代，层序遍历，计算每层的平均值记录到res数组，最后返回res数组。神奇的地方在于不能在累加的时候先除以count，而是先累加到一起再除，不然通不过case。

python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        res = []
        if not root:
            return res
        queue = collections.deque()
        queue.append(root)
        while queue:
            result = 0
            n = len(queue)
            for _ in range(len(queue)):
                p = queue.popleft()
                result += p.val
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            res.append(result/n)
        return res

C++:

/**
 * 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) {
        if (!root){
            return {};
        }
        vector<double> res;
        queue<TreeNode*> q{{root}};

        while(!q.empty()){
            double total = 0;
            int count = q.size();
            for (int i=0;i<count;i++){
                TreeNode *p = q.front();
                q.pop();
                total += p->val;
                if (p->left){
                    q.push(p->left);
                }
                if (p->right){
                    q.push(p->right);
                }
            }
            res.push_back(total/count);

        }
        return res;


    }
};

参考：
[LeetCode] 637. Average of Levels in Binary Tree 二叉树的层平均值