C++의 트리에서 주어진 하위 트리의 DFS 순회에서 K 번째 노드 찾기

이 문제에서는 크기가 N인 트리, 트리 V와 k의 노드가 제공됩니다. 우리의 작업은 트리에서 주어진 하위 트리의 DFS 순회에서 K번째 노드를 찾는 것입니다. .

정점 V에서 시작하는 트리의 DFS 순회에서 k번째 노드를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

V =2, k =3

출력 :4

설명 -

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

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 노드 V의 DFS 순회를 찾고 여기서 k번째 값을 출력하는 것입니다.

이를 위해 우리는 트리의 DFS 순회를 수행하고 벡터에 저장합니다. 이 벡터에서 V_start 값을 찾습니다. 및 V_end 트리의 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