Trung bình các cấp độ trong cây nhị phân C++

Mô tả bài toán

Cho cây nhị phân không rỗng. Tìm trung bình giá trị các nút tại mỗi cấp độ (level), trả về mảng các giá trị trung bình.

Ví dụ: Cây gốc 3, cấp 1: 9,20; cấp 2: 15,7 → Trung bình: [3, 14.5, 11].

Giải pháp (BFS - Duyệt theo cấp)

• Dùng hàng đợi (queue) duyệt BFS.
• Mỗi cấp độ: lấy kích thước queue, duyệt đúng số lượng đó, tính tổng, push con vào queue.
• Tính trung bình cấp độ, thêm vào kết quả.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<float> v) {
    cout << "[";
    for (float x : v) cout << x << ", ";
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void insert(TreeNode** root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while (q.size()) {
        TreeNode* temp = q.front(); q.pop();
        if (!temp->left) { temp->left = val ? new TreeNode(val) : new TreeNode(0); return; }
        else q.push(temp->left);
        if (!temp->right) { temp->right = val ? new TreeNode(val) : new TreeNode(0); return; }
        else q.push(temp->right);
    }
}

TreeNode* make_tree(vector<int> v) {
    TreeNode* root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

class Solution {
public:
    vector<float> averageOfLevels(TreeNode* root) {
        vector<float> result;
        queue<TreeNode*> q; q.push(root);
        while (!q.empty()) {
            int n = q.size();
            double sum = 0;
            for (int i = 0; i < n; i++) {
                TreeNode* t = q.front(); q.pop();
                sum += t->val;
                if (t->left && t->left->val != 0) q.push(t->left);
                if (t->right && t->right->val != 0) q.push(t->right);
            }
            result.push_back(sum / n);
        }
        return result;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,9,20,0,0,15,7};
    TreeNode* root = make_tree(v);
    print_vector(ob.averageOfLevels(root));
    return 0;
}

Đầu vào

{3,9,20,NULL,NULL,15,7}

Đầu ra

[3, 14.5, 11, ]