637. Average of Levels in Binary Tree

題目網址：https://leetcode.cn/problems/average-of-levels-in-binary-tree/

題意：給一 Binary Tree(BT), 計算每一層的平均值。

Solution：

想法：利用 BFS

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) {
            return {};
        }

        vector<double> res;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            const int size = q.size();
            double sum = 0;

            for (int i = 0; i < size; ++i) {
                const auto node = q.front();
                q.pop();

                sum += node->val;
                if (node->left) {
                    q.push(node->left);
                }

                if (node->right) {
                    q.push(node->right);
                }
            }

            res.emplace_back(sum / size);
        }

        return res;
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ 取決於樹的高度, worse case 為 skew tree, tree