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

ภาพรวมปัญหา

ได้รับ Binary Tree และ K ต้องพิมพ์โหนดที่ห่างจาก Leaf Node ระยะ K (นับขึ้นไปยัง Ancestor)

ตัวอย่าง

K = 2

Output: 6 9

วิธีแก้ปัญหา (DFS + Path Tracking)

1. DFS เก็บ Path (Ancestors) ในอาร์เรย์
2. ตอนเจอ Leaf → ดู Path[pathLen - K - 1] คือโหนดที่ห่าง K
3. ใช้ Visited array ป้องกันพิมพ์ซ้ำ

Time Complexity: O(n)

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

#include <iostream>
using namespace std;

#define MAX_HEIGHT 10000

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

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

void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k) {
    if (node == NULL) return;
    path[pathLen] = node->key;
    visited[pathLen] = false;
    pathLen++;
    if (node->left == NULL && node->right == NULL && pathLen - k - 1 >= 0 && visited[pathLen - k - 1] == false) {
        cout << path[pathLen - k - 1] << "\t";
        visited[pathLen - k - 1] = true;
        return;
    }
    nodesKatDistance(node->left, path, visited, pathLen, k);
    nodesKatDistance(node->right, path, visited, pathLen, k);
}

void printNodes(Node* node, int k) {
    int path[MAX_HEIGHT];
    bool visited[MAX_HEIGHT] = {false};
    nodesKatDistance(node, path, visited, 0, k);
}

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->left->left = insertNode(5);
    root->right->left->right = insertNode(1);
    int k = 2;
    cout << "All nodes at distance " << k << " from leaf node are:\n";
    printNodes(root, k);
    return 0;
}

ผลลัพธ์ (Output)

All nodes at distance 2 from the leaf node are:
6 9