Tìm tổng cấp lớn nhất trong cây nhị phân C++

Giới thiệu

Cho cây nhị phân có giá trị node dương/âm. Tìm cấp (level) có tổng giá trị node lớn nhất.

Ví dụ

       3
     /   \
   -3     4
  / \   / \
 5  -1 6  -5

Level 1: 3

Level 2: -3 + 4 = 1

Level 3: 5 + (-1) + 6 + (-5) = 5 ← MAX

Thuật toán: Level Order Traversal (BFS)

Duyệt theo cấp độ (BFS) dùng queue. Với mỗi cấp, tính tổng và cập nhật max.

Mã nguồn hoàn chỉnh

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

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

int findMaxLevelSum(Node* root) {
    if (!root) return 0;
    
    int maxSum = root->data;
    queue q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        int levelSum = 0;
        
        while (levelSize--) {
            Node* node = q.front(); q.pop();
            levelSum += node->data;
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        maxSum = max(maxSum, levelSum);
    }
    
    return maxSum;
}

int main() {
    Node* root = newNode(3);
    root->left = newNode(-3);
    root->right = newNode(4);
    root->left->left = newNode(5);
    root->left->right = newNode(-1);
    root->right->left = newNode(6);
    root->right->right = newNode(-5);
    
    cout << "Tong cap lon nhat: " << findMaxLevelSum(root) << endl;
    return 0;
}

Kết quả chạy chương trình

Tong cap lon nhat: 5

Phân tích độ phức tạp

• Thời gian: O(n) - thăm mỗi node 1 lần
• Không gian: O(w) - w = độ rộng tối đa (queue)

Mở rộng: Trả về cả cấp độ có tổng lớn nhất

pair findMaxLevelSumWithLevel(Node* root) {
    if (!root) return {0, 0};
    
    queue q;
    q.push(root);
    int maxSum = root->data, maxLevel = 1, level = 1;
    
    while (!q.empty()) {
        int sz = q.size(), sum = 0;
        while (sz--) {
            Node* n = q.front(); q.pop();
            sum += n->data;
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        if (sum > maxSum) {
            maxSum = sum;
            maxLevel = level;
        }
        level++;
    }
    return {maxLevel, maxSum};
}

Kết luận

BFS (Level Order Traversal) là phương pháp tự nhiên nhất cho bài toán theo cấp độ. Độ phức tạp tuyến tính, dễ cài đặt, dễ mở rộng.