Chương trình tìm cấp độ cây nhị phân có tổng nhỏ nhất trong C++

Cho một cây nhị phân, cấp độ của gốc là 1, cấp độ của các nút con là 2, v.v. Tìm cấp độ nhỏ nhất X sao cho tổng giá trị các nút tại cấp độ X là nhỏ nhất.

Ví dụ: cây có gốc 5, trái 4, phải -10, ... → cấp độ 2 có tổng 4 + (-10) = -6 (nhỏ nhất) → kết quả 2.

Thuật toán (BFS)

• Khởi tạo level = 1, sum = root->val, ansLevel = 1, ansSum = sum.
• Dùng hàng đợi (queue) để duyệt theo cấp độ (BFS).
• Với mỗi cấp độ: tính tổng giá trị các nút, so sánh với ansSum, cập nhật nếu nhỏ hơn.
• Trả về ansLevel.

Ví dụ triển khai (C++)

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

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

class Solution {
public:
    int solve(TreeNode* r) {
        int level = 1, sum = r->val;
        int ansLevel = level, ansSum = sum;
        queue<TreeNode*> q;
        q.push(r);
        while (!q.empty()) {
            int capacity = q.size();
            level++;
            sum = 0;
            while (capacity--) {
                TreeNode* node = q.front(); q.pop();
                if (node->right) { sum += node->right->val; q.push(node->right); }
                if (node->left)  { sum += node->left->val;  q.push(node->left);  }
            }
            if (ansSum > sum) { ansSum = sum; ansLevel = level; }
        }
        return ansLevel;
    }
};

int main() {
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(-10);
    root->left->right = new TreeNode(-2);
    root->right->left = new TreeNode(-7);
    root->right->right = new TreeNode(15);
    Solution ob;
    cout << ob.solve(root);
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(5); root->left = new TreeNode(4); root->right = new TreeNode(-10); root->left->right = new TreeNode(-2); root->right->left = new TreeNode(-7); root->right->right = new TreeNode(15);

Đầu ra

2