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