Tích các nút tại cấp k trong cây biểu diễn bằng chuỗi trong C++

Cho cây nhị phân biểu diễn dưới dạng chuỗi ký tự, nhiệm vụ là tìm tích các nút tại cấp (level) k. Mỗi nút có: dữ liệu, con trỏ trái, con trỏ phải.

Cấp của cây nhị phân bắt đầu từ 0. Cho cấp k, tính tích các nút ở cấp đó.

Ví dụ: k=2, nút ở cấp 2 là 40, 50, 60 → Tích = 40*50*60 = 120,000

Đầu vào 1

"(1(2(3()())(4()(5()())))(6(7()())(8()())))" K = 1

Đầu ra 1

Tích nút cấp k = 12

Đầu vào 2

"(0(5(6()())(4()(9()())))(7(1()())(3()())))" k = 2

Đầu ra 2

Tích nút cấp k = 72

Thuật toán

Duyệt chuỗi, theo dõi cấp độ bằng cách đếm dấu '(' và ')'. Khi gặp ký tự số tại cấp k, nhân vào tích.

int tichCapK(string cay, int k) {
    int cap = -1;
    int tich = 1;
    int n = cay.length();
    for (int i = 0; i < n; i++) {
        if (cay[i] == '(') cap++;
        else if (cay[i] == ')') cap--;
        else {
            if (cap == k)
                tich *= (cay[i] - '0');
        }
    }
    return tich;
}

Ví dụ mã nguồn

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

int tichCapK(string cay, int k) {
    int cap = -1;
    int tich = 1;
    int n = cay.length();
    for (int i = 0; i < n; i++) {
        if (cay[i] == '(') cap++;
        else if (cay[i] == ')') cap--;
        else {
            if (cap == k)
                tich *= (cay[i] - '0');
        }
    }
    return tich;
}

int main() {
    string cay = "(1(2(3()())(4()(5()())))(6(7()())(8()())))";
    int k = 1;
    cout << "Tích nút cấp k = " << tichCapK(cay, k);
    return 0;
}

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

Tích nút cấp k = 12