พิมพ์โหนดที่มี Leaf Nodes จำนวน K ใน Binary Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree และ K ต้องพิมพ์โหนดที่มี Leaf Nodes ใน Subtree จำนวน K ตัว

ตัวอย่าง

K = 2

Output: N T

วิธีแก้ปัญหา (Postorder Traversal)

1. Postorder Traversal คืนจำนวน Leaf ใน Subtree
2. ถ้า leftLeaves + rightLeaves == K → พิมพ์โหนดปัจจุบัน
3. Time Complexity: O(n)

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

#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 << "Nodes with " << K << " leaves are:\n";
    nodeWithKLeave(root, K);
    return 0;
}

ผลลัพธ์ (Output)

Nodes with 2 leaves are:
N T