Maximum Sum of Non-Leaf Nodes Among All Levels ใน Binary Tree (C++)

ปัญหา

มี Binary Tree หาผลรวมของโหนดที่ไม่ใช่ใบ (non-leaf nodes) ในแต่ละระดับ แล้วหาค่าสูงสุด

ตัวอย่าง

Level 1: 4, Level 2: 1+2=3, Level 3: 9 (4,7 เป็นใบ), Level 4: 0 → Max = 9

อัลกอริทึม (Level Order Traversal + Queue)

1. ถ้า root == NULL → return 0
2. maxSum = root->data
3. Queue q, push root
4. while q ไม่ว่าง:
   • count = q.size(), levelSum = 0
   • วน count รอบ:
     • temp = q.front(), q.pop()
     • ถ้า temp มี left หรือ right → levelSum += temp->data
     • push left/right เข้า queue ถ้ามี
   • maxSum = max(maxSum, levelSum)
5. return maxSum

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

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

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

int maxLevelSum(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();
            if (temp->left != NULL || temp->right != NULL)
                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;
}

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

int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(1);
    root->right = insertNode(2);
    root->left->left = insertNode(4);
    root->left->right = insertNode(7);
    root->right->right = insertNode(9);
    root->right->right->left = insertNode(5);
    cout << "The maximum sum of all non-leaf nodes at a level of the binary tree is " << maxLevelSum(root);
    return 0;
}

ผลลัพธ์

The maximum sum of all non-leaf nodes at a level of the binary tree is 9