题解 | #牛群平均重量#

考察知识点： 队列、广度优先搜索

​题目分析：

​ 为了求出每一层的平均重量，需要知道每一层中牛的数量和牛的重量总和。这种一层一层的遍历方式即为广度优先搜索。广度优先搜索一般使用一个队列，首先将根节点放入队列，然后先看队列中有几个值，也就是说这一层有多少个节点。然后对这几个节点进行访问，对于其中的每个节点，如果他有左子树，就将左子树放入队列中；如果有右子树，再把右子树放入队列中。

​ 当这几个节点遍历完后，相当于遍历了这一层，就能够求取平均值。此时因为二叉树可能没有遍历完，后面还有几层，所以会重复上述操作，直至队列中没有元素。​

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return double浮点型vector
     */
    vector<double> averageOfLevels(TreeNode* root) {
        // write code here
        if (!root) return {};
        vector<double> res;
        queue<TreeNode*> cows;
        cows.push(root);
        while (!cows.empty()) {
            int size = cows.size();
            int sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode *p = cows.front();
                sum += p->val;
                cows.pop();
                if (p->left) cows.push(p->left);
                if (p->right) cows.push(p->right);
            }
            res.push_back((double)sum / size);
        }
        return res;
    }
};