Tích các nút lá trong cây nhị phân trong C++

Cho cây nhị phân, nhiệm vụ là tìm tích của tất cả các nút lá (leaf nodes).

Nút lá là nút không có con (left và right đều NULL). Nút gốc chỉ là cha, không phải con.

Đầu vào (cây như hình)

Đầu ra

Các nút lá: 23, 34, 25
Tích = 23 * 34 * 25 = 19550

Phương pháp tiếp cận

• Nhập dữ liệu nút
• Duyệt cây từ gốc
• Kiểm tra nút lá (left == NULL && right == NULL) thì nhân vào tích
• In kết quả

Thuật toán

void tichNutLa(Node* root, int &tich) {
    if (!root) return;
    if (!root->left && !root->right)
        tich *= root->data;
    tichNutLa(root->left, tich);
    tichNutLa(root->right, tich);
}

Ví dụ mã nguồn

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

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

Node* taoNut(int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void tichNutLa(Node* root, int &tich) {
    if (!root) return;
    if (!root->left && !root->right)
        tich *= root->data;
    tichNutLa(root->left, tich);
    tichNutLa(root->right, tich);
}

int main() {
    Node* root = taoNut(10);
    root->left = taoNut(20);
    root->left->left = taoNut(30);
    root->left->right = taoNut(40);
    root->right = taoNut(50);
    root->right->right = taoNut(60);
    root->right->left = taoNut(70);
    
    int tich = 1;
    tichNutLa(root, tich);
    cout << "Tích các nút lá: " << tich;
    return 0;
}

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

Tích các nút lá: 5040000