# Leetcode [637] Average of Levels in Binary Tree (Easy)

## 題目

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

## 思路
+ 一看到這個題目其實很簡單的就是要用BFS來做計算
+ 那比較重要的就是去計算每一層的總和
+ queue跟BFS搭配的時候一個很重要的特性就是
+ 我們可以透過`int levelSize = q.size();` 來計算每一層的node數量，接著使用for迴圈搭配q.front()去iter每一個node
+ 計算好總合以後，就可以去計算平均了！

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> sol;
        if(root == nullptr) {return sol;}
        BFS(root, sol);
        return sol; 
    }
    
    void BFS(TreeNode* root, vector<double>& sol)
    {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int levelSize = q.size(); // remember that the size of queue is the number of the level!!!
            double sum = 0;
            for(int i = 0; i < levelSize; i++)
            {
                TreeNode* tmp = q.front();
                sum += tmp->val;
                if(tmp->left != nullptr)
                {
                    q.push(tmp->left);
                }
                if(tmp->right != nullptr)
                {
                    q.push(tmp->right);
                }
                q.pop();
            }
            sol.emplace_back(sum/(double)levelSize);
        }
    }
};

### 解法分析
+ time complexity: O(n^2)

### 執行結果