In Tất Cả Nút Có K Nút Lá Trong Cây Nhị Phân Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và một số nguyên K. In tất cả nút của cây nhị phân có K nút lá trong cây con của chúng.

Cây nhị phân là cây đặc biệt mà mỗi nút có tối đa 2 nút con.

Nút lá của cây nhị phân là nút ở cuối cây.

Ví dụ để hiểu vấn đề:

K = 2

Đầu ra – {S}

Để giải quyết, ta duyệt cây (postorder). Xem cây con trái và phải, nếu tổng lá = K, in nút hiện tại ngược lại gọi đệ quy đếm lá của cây con.

Giải pháp dựa trên duyệt nên độ phức tạp tỷ lệ với kích thước cây. Độ phức tạp thời gian – O(n).

Ví Dụ

Chương trình triển khai giải pháp:

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

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

struct Node* insertNode(char data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

int nodeWithKLeave(struct Node* ptr, int k) {
    if (ptr == NULL)
        return 0;
    if (ptr->left == NULL && ptr->right == NULL)
        return 1;
    int total = nodeWithKLeave(ptr->left, k) + nodeWithKLeave(ptr->right, k);
    if (k == total)
        cout << ptr->data << " ";
    return total;
}

int main() {
    struct Node* root = insertNode('A');
    root->left = insertNode('B');
    root->right = insertNode('K');
    root->left->left = insertNode('N');
    root->left->right = insertNode('S');
    root->left->left->left = insertNode('X');
    root->left->left->right = insertNode('H');
    root->right->right = insertNode('E');
    root->right->left = insertNode('T');
    root->right->left->left = insertNode('O');
    root->right->left->right = insertNode('P');
    int K = 2;
    cout << "Các nút với " << K << " lá là:\n";
    nodeWithKLeave(root, K);
    return 0;
}

Đầu Ra

Các nút với 2 lá là: N T