ค้นหาโหนด Kth ในการข้ามผ่าน DFS ของทรีย่อยที่กำหนดในทรีใน C++

ในปัญหานี้ เราได้ต้นไม้ขนาด N ซึ่งเป็นโหนดของต้นไม้ V และ k งานของเราคือ ค้นหาโหนด Kth ในการข้ามผ่าน DFS ของทรีย่อยที่ระบุในทรี .

เราจำเป็นต้องค้นหาโหนด kth ในการข้ามผ่าน DFS ของต้นไม้โดยเริ่มจากจุดยอด V

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ข้อมูลเข้า :

V =2, k =3

เอาท์พุต :4

คำอธิบาย −

The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5.

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือค้นหา DFS traversal ของโหนด V และพิมพ์ค่า kth จากสิ่งนี้

สำหรับสิ่งนี้ เราทำการข้ามผ่าน DFS ของทรีและจัดเก็บไว้ในเวกเตอร์ ในเวกเตอร์นี้ เราจะพบค่าสำหรับ V_start และวี_จบ ทำเครื่องหมายจุดเริ่มต้นและจุดสิ้นสุดของการข้ามผ่าน DFS ของแผนผัง จากนั้นให้หาค่าที่ k ในช่วงนี้และพิมพ์ออกมาถ้าเป็นไปได้

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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