इस समस्या में, हमें N आकार का एक पेड़, V और k के पेड़ का एक नोड दिया जाता है। हमारा काम है किसी ट्री में दिए गए सबट्री के DFS ट्रैवर्सल में Kth नोड ढूंढना ।
हमें शीर्ष V से शुरू होने वाले पेड़ के DFS ट्रैवर्सल में kth नोड खोजने की आवश्यकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :
वी =2, के =3
आउटपुट :4
स्पष्टीकरण -
The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5. समाधान दृष्टिकोण
समस्या का एक सरल समाधान है नोड V का DFS ट्रैवर्सल ढूंढना और इससे kth मान प्रिंट करना।
इसके लिए हम ट्री का DFS ट्रैवर्सल करते हैं और उसे एक वेक्टर में स्टोर करते हैं। इस वेक्टर में, हम Vstart . के लिए मान पाएंगे और वी<उप>समाप्त ट्री के DFS ट्रैवर्सल के प्रारंभ और अंत को चिह्नित करना। फिर इस श्रेणी में k-th मान ज्ञात करें और यदि संभव हो तो इसे प्रिंट करें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
vector<int> tree[N];
int currentIdx;
vector<int> startIdx,endIdx;
vector<int> dfsTraversalVector;
void insertEdge(int u, int v){
tree[u].push_back(v);
tree[v].push_back(u);
}
void findDfsTraversal(int ch, int par){
dfsTraversalVector[currentIdx] = ch;
startIdx[ch] = currentIdx++;
for (auto c : tree[ch]) {
if (c != par)
findDfsTraversal(c, ch);
}
endIdx[ch] = currentIdx - 1;
}
int findKNodeDfsV(int v, int k){
k = k + (startIdx[v] - 1);
if (k <= endIdx[v])
return dfsTraversalVector[k];
return -1;
}
int main(){
n = 9;
insertEdge(5, 8);
insertEdge(5, 2);
insertEdge(5, 10);
insertEdge(5, 3);
insertEdge(2, 6);
insertEdge(2, 1);
insertEdge(3, 9);
insertEdge(6, 1);
insertEdge(9, 7);
startIdx.resize(n);
endIdx.resize(n);
dfsTraversalVector.resize(n);
findDfsTraversal(5, 0);
int v = 2,
k = 4;
cout<<k<<"-th node in DFS traversal of node "<<v<<" is "<<findKNodeDfsV(v, k);
return 0;
} आउटपुट
4-th node in DFS traversal of node 2 is 1