ในปัญหานี้ เราจะได้รับไบนารีทรี โหนดเป้าหมาย และจำนวนเต็ม K เราต้องพิมพ์โหนดทั้งหมดของทรีที่ระยะห่าง K จากโหนดเป้าหมาย .
ต้นไม้ไบนารี เป็นต้นไม้พิเศษที่แต่ละโหนดมีโหนดสูงสุดสองโหนด (หนึ่ง/สอง/ไม่มี)
มาดูตัวอย่างทำความเข้าใจปัญหากัน
K =2
โหนดเป้าหมาย:9
ผลผลิต −
5 1 3.
คำอธิบาย −
สามารถใช้ระยะทางสำหรับโหนดที่สูงขึ้น ต่ำลง หรือในระดับเดียวกันได้ ดังนั้นเราจะส่งคืนโหนดตามลำดับ
เพื่อแก้ปัญหานี้ เราต้องเข้าใจว่าโหนดประเภทใดที่มีระยะห่าง K ห่างจากโหนดเป้าหมาย
จากการทดสอบข้างต้น เราจะเห็นว่าโหนดที่อยู่ห่างไกล k สามารถอยู่ในทรีย่อยของโหนดเป้าหมาย (5 และ 1) หรือที่ใดก็ได้ในทรีย่อยของบรรพบุรุษของโหนดเป้าหมาย (3)
ตอนนี้ วิธีการหาวิธีแก้ปัญหาของกรณีแรกคือโดยการสำรวจทรีย่อยของโหนดเป้าหมาย และตรวจสอบว่าระยะห่างของโหนดจากเป้าหมายคือ K หรือไม่ ถ้าใช่ ให้พิมพ์โหนด
สำหรับกรณีที่ 2 เราต้องตรวจสอบโหนดบรรพบุรุษและทรีย่อยของบรรพบุรุษเหล่านี้เพื่อหาเป้าหมายและพิมพ์ทั้งหมดในระยะ K จากจุดนั้น
โปรแกรมด้านล่างจะแสดงการใช้งานโซลูชันของเรา -
ตัวอย่าง
#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 << endl;
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;
} ผลลัพธ์
Nodes at distance 2 from the target n tode are − 5 1 3
