พิมพ์โหนดที่ห่างจากโหนดเป้าหมาย K ระยะใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree, Target Node, และ K ต้องพิมพ์โหนดที่ห่างจาก Target Node ระยะ K

ตัวอย่าง

K = 2, Target: 9

Output: 5 1 3

วิธีแก้ปัญหา

โหนดที่ห่าง K อาจอยู่ใน:

1. Subtree ของ Target → DFS ลงไปหา depth K
2. Subtree ของ Ancestor → หา Ancestor แล้วไปอีกฝั่ง

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

#include <iostream>
using namespace std;

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

void printSubtreeNodes(node* root, int k) {
    if (root == NULL || k < 0) return;
    if (k == 0) {
        cout << root->data << "\t";
        return;
    }
    printSubtreeNodes(root->left, k - 1);
    printSubtreeNodes(root->right, k - 1);
}

int printKNodes(node* root, node* target, int k) {
    if (root == NULL) return -1;
    if (root == target) {
        printSubtreeNodes(root, k);
        return 0;
    }
    int dl = printKNodes(root->left, target, k);
    if (dl != -1) {
        if (dl + 1 == k) cout << root->data << "\t";
        else printSubtreeNodes(root->right, k - dl - 2);
        return 1 + dl;
    }
    int dr = printKNodes(root->right, target, k);
    if (dr != -1) {
        if (dr + 1 == k) cout << root->data << "\t";
        else printSubtreeNodes(root->left, k - dr - 2);
        return 1 + dr;
    }
    return -1;
}

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

int main() {
    node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->right = insertNode(4);
    root->right->left = insertNode(8);
    root->right->right = insertNode(10);
    root->right->right->left = insertNode(5);
    root->right->right->right = insertNode(1);
    node* target = root->right;
    int K = 2;
    cout << "Nodes at distance " << K << " from the target node are:\n";
    printKNodes(root, target, K);
    return 0;
}

ผลลัพธ์ (Output)

Nodes at distance 2 from the target node are:
5 1 3