โปรแกรมหาผลคูณโหนดระดับ k ในต้นไม้ที่แสดงเป็นสตริง C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลคูณของโหนดที่อยู่ในระดับ (level) k ของ Binary Tree ที่ถูกเข้ารหัสเป็นสตริง รูปแบบสตริงใช้วงเล็บแสดงโครงสร้างต้นไม้

รูปแบบสตริงแทนต้นไม้

รูปแบบ: (root(left_subtree)(right_subtree))

• () แทนโหนดว่าง (NULL)
• ตัวเลขแทนค่าข้อมูลของโหนด (สมมติเป็นหลักเดียว 0-9)
• ระดับเริ่มจาก 0 ที่ราก (root)

ตัวอย่างการแปลง

Tree:      1           String: (1(2(3()())(4()(5()())))(6(7()())(8()())))
           / \                    Level 0: 1
          2   6                   Level 1: 2, 6  → Product = 12
         / \ / \                  Level 2: 3, 4, 7, 8
        3  4 7  8
         \     \
          5     (Level 3: 5)

อัลกอริทึม

1. เริ่มต้น level = -1 (ก่อนอ่านวงเล็บเปิดแรกของราก)
2. อ่านสตริงทีละตัวอักษร:
   • เจอ ( → level++
   • เจอ ) → level--
   • เจอตัวเลข → ถ้า level == k ให้นำไปคูณ
3. คืนค่าผลคูณสะสม

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

#include <iostream>
#include <string>
using namespace std;

int productAtLevelK(string tree, int k) {
    int level = -1;
    int product = 1;
    bool found = false;
    
    for (char c : tree) {
        if (c == '(') {
            level++;
        } else if (c == ')') {
            level--;
        } else if (isdigit(c)) {
            if (level == k) {
                product *= (c - '0');
                found = true;
            }
        }
    }
    
    return found ? product : 0;  // คืน 0 ถ้าไม่มีโหนดในระดับ k
}

int main() {
    // ตัวอย่างที่ 1
    string tree1 = "(1(2(3()())(4()(5()())))(6(7()())(8()())))";
    int k1 = 1;
    cout << "Tree: " << tree1 << endl;
    cout << "Level " << k1 << " product = " << productAtLevelK(tree1, k1) << endl;
    // Level 1: nodes 2, 6 → 2*6 = 12
    
    cout << endl;
    
    // ตัวอย่างที่ 2
    string tree2 = "(0(5(6()())(4()(9()())))(7(1()())(3()())))";
    int k2 = 2;
    cout << "Tree: " << tree2 << endl;
    cout << "Level " << k2 << " product = " << productAtLevelK(tree2, k2) << endl;
    // Level 2: nodes 6, 4, 1, 3 → 6*4*1*3 = 72
    
    cout << endl;
    
    // ทดสอบระดับต่างๆ
    for (int k = 0; k <= 3; k++) {
        cout << "Level " << k << " product = " << productAtLevelK(tree1, k) << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Tree: (1(2(3()())(4()(5()())))(6(7()())(8()())))
Level 1 product = 12

Tree: (0(5(6()())(4()(9()())))(7(1()())(3()())))
Level 2 product = 72

Level 0 product = 1
Level 1 product = 12
Level 2 product = 168
Level 3 product = 5

การวิเคราะห์ตัวอย่างที่ 1 รายละเอียด

ข้อจำกัดของวิธีนี้

• รองรับเฉพาะตัวเลข 1 หลัก (0-9) เท่านั้น
• ไม่รองรับตัวเลขลบ หรือหลายหลัก
• รูปแบบสตริงต้องถูกต้องสมบูรณ์ (well-formed parentheses)

การขยายเพื่อรองรับหลายหลัก

// แก้ไขส่วนอ่านตัวเลข
else if (isdigit(c)) {
    // อ่านตัวเลขเต็มจำนวน (หลายหลัก)
    int num = 0;
    int start = i;
    while (i < tree.length() && isdigit(tree[i])) {
        num = num * 10 + (tree[i] - '0');
        i++;
    }
    i--; // ปรับดัชนีเพราะ for loop จะ i++ อีกครั้ง
    
    if (level == k) {
        product *= num;
        found = true;
    }
}

ความซับซ้อนของอัลกอริทึม

• เวลา: O(L) โดย L = ความยาวสตริง
• พื้นที่: O(1) - ใช้ตัวแปรคงที่
• ไม่ต้องสร้างโครงสร้างต้นไม้จริง ประหยัดหน่วยความจำ