หาผลรวมระดับสูงสุดใน Binary Tree ใน C++

บทนำ

โจทย์: หาระดับ (Level) ของ Binary Tree ที่มีผลรวมค่าโหนดมากที่สุด (รองรับค่าลบได้)

ขั้นตอนการแก้ปัญหา

1. Level Order Traversal (BFS) ด้วย Queue
2. แต่ละรอบ while: ประมวลผลโหนดทั้งหมดในระดับนั้น (นับด้วย queue size)
3. คำนวณผลรวมระดับ (levelSum)
4. อัปเดต maxSum = max(maxSum, levelSum)

ตัวอย่างโค้ด

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

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

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

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

int main() {
    struct 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 << "The sum of level with maximum level sum is " << findMaxLevelSum(root);
    return 0;
}

ผลลัพธ์

The sum of level with maximum level sum is 5

คำอธิบายต้นไม้ตัวอย่าง

Level 1: 3 → sum = 3
Level 2: -3, 4 → sum = 1
Level 3: 5, -1, 6, -5 → sum = 5 ← สูงสุด

สรุป

BFS Level Order Traversal เป็นวิธีมาตรฐานสำหรับโจทย์ระดับ (Level) ของต้นไม้ ใช้ Queue จัดการโหนดแต่ละระดับ