Tổng mức lớn nhất của cây nhị phân trong C++

Cho gốc cây nhị phân, cấp gốc = 1, cấp con = 2, ... Tìm cấp nhỏ nhất X có tổng giá trị nút lớn nhất.

Ví dụ: cây [1,7,0,7,-8,null,null] → Cấp 1: 1, Cấp 2: 7+0=7, Cấp 3: 7+(-8)=-1 → Max ở cấp 2 → Kết quả: 2.

Giải thuật (BFS theo cấp)

1. Khởi tạo level=1, sum=root->val, ansLevel=1, ansSum=sum.
2. Hàng đợi q chứa root.
3. Khi q không rỗng:
4. capacity = q.size(), level++, sum=0.
5. Xử lý capacity nút: pop, cộng giá trị con vào sum, push con vào q.
6. Nếu sum > ansSum, cập nhật ansSum, ansLevel.
7. Trả về ansLevel.

Ví dụ C++

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

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) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0); return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = 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:
    int maxLevelSum(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() {
    vector<int> v = {1,7,0,7,-8,NULL,NULL};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << ob.maxLevelSum(root);
    return 0;
}

Đầu vào

[1,7,0,7,-8,null,null]

Đầu ra

2