หาผลคูณของผลรวมข้อมูลใบ (Leaves) ในระดับเดียวกันของ Binary Tree ใน C++

แนวคิด

กำหนด Binary Tree ต้องคืนค่า:

• แต่ละระดับ คำนวณผลรวมของใบ (leaves) ทั้งหมดในระดับนั้น (ถ้าไม่มีใบ ข้ามไป)
• นำผลรวมแต่ละระดับมาคูณกัน แล้วคืนค่า

ตัวอย่างที่ 1

Tree:

    3
   / \
  8   6
       \
        10

ตัวอย่างที่ 2

Tree:

        3
       / \
      8   6
     / \   \
    9   7   10
   / \   / \
  2  12 5  11

วิธีแก้ปัญหา

• Simple Solution: คำนวณผลรวมใบแต่ละระดับแบบ Recursive แล้วคูณกัน → O(n²)
• Efficient Solution: ใช้ Queue ทำ Level Order Traversal แยกระดับชัดเจน ตรวจสอบใบในแต่ละระดับ คำนวณผลรวม แล้วคูณสะสม → O(n)

โค้ดตัวอย่าง (Iterative, Queue-based)

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

struct Node1 {
    int data1;
    struct Node1 *left1, *right1;
};

bool isLeaf(Node1* root1) {
    return (!root1->left1 && !root1->right1);
}

int sumAndMultiplyLevelData(Node1* root1) {
    if (!root1) return 0;
    int mul1 = 1;
    
    queue<Node1*> q1;
    q1.push(root1);
    
    while (1) {
        int NodeCount1 = q1.size();
        if (NodeCount1 == 0) break;
        
        int levelSum1 = 0;
        bool leafFound1 = false;
        
        while (NodeCount1 > 0) {
            Node1* node = q1.front();
            if (isLeaf(node)) {
                leafFound1 = true;
                levelSum1 += node->data1;
            }
            q1.pop();
            if (node->left1 != NULL) q1.push(node->left1);
            if (node->right1 != NULL) q1.push(node->right1);
            NodeCount1--;
        }
        
        if (leafFound1)
            mul1 *= levelSum1;
    }
    return mul1;
}

Node1* newNode(int data1) {
    Node1* temp1 = new Node1;
    temp1->data1 = data1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

int main() {
    Node1* root1 = newNode(3);
    root1->left1 = newNode(8);
    root1->right1 = newNode(6);
    root1->left1->right1 = newNode(7);
    root1->left1->left1 = newNode(9);
    root1->left1->right1->left1 = newNode(2);
    root1->left1->right1->right1 = newNode(12);
    root1->right1->right1 = newNode(10);
    root1->right1->right1->left1 = newNode(5);
    root1->right1->right1->right1 = newNode(11);
    
    cout << "Final product value = " << sumAndMultiplyLevelData(root1) << endl;
    return 0;
}

ผลลัพธ์

Final product value = 270