Tìm tích của tổng các lá ở cùng cấp trong cây nhị phân trong C++

Khái niệm

Cho cây nhị phân. Với mỗi cấp, tính tổng giá trị các nút lá (nếu có). Tính tích của tất cả các tổng đó.

Ví dụ 1

Đầu vào: Cây: 3 (gốc), trái 8, phải 6, 8 có con phải 10.

Đầu ra: 80

Cấp 1 không có lá. Cấp 2 có lá 8. Cấp 3 có lá 10. Kết quả: 8 * 10 = 80.

Ví dụ 2

Đầu vào: Cây phức tạp hơn.

Đầu ra: 270

Cấp 3 có lá 9. Cấp cuối có 4 lá: 2, 12, 5, 11. Tổng = 30. Kết quả: 9 * 30 = 270.

Phương pháp

Cách đơn giản: Đệ quy tính tổng lá mỗi cấp từ trên xuống, sau đó nhân. Độ phức tạp O(n²).

Cách hiệu quả: Duyệt theo cấp (level order) dùng Queue. Xử lý từng cấp riêng biệt, kiểm tra có lá không, tính tổng lá cấp đó. Cuối cùng nhân các tổng.

Ví dụ

#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* Node1 = q1.front();
            if (isLeaf(Node1)) {
                leafFound1 = true;
                levelSum1 += Node1->data1;
            }
            q1.pop();
            if (Node1->left1 != NULL) q1.push(Node1->left1);
            if (Node1->right1 != NULL) q1.push(Node1->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 << "Giá trị tích cuối cùng = " << sumAndMultiplyLevelData(root1) << endl;
    return 0;
}

Đầu ra

Giá trị tích cuối cùng = 270