Tìm nút thứ k trong duyệt DFS của cây con trong C++

Cho cây N nút, nút V và số k. Nhiệm vụ: tìm nút thứ k trong duyệt DFS của cây con gốc tại V.

Ví dụ minh họa

Cây (hình ảnh), V = 2, k = 3 → Output: 4

DFS từ 2: {2, 3, 5, 6, 7}, phần tử thứ 3 là 5 (0-indexed) hoặc 4 (1-indexed tùy implement).

Phương pháp giải

Thực hiện DFS từ gốc, lưu thứ tự duyệt trong vector. Ghi nhận startIdx và endIdx của mỗi nút trong vector DFS. Nút thứ k của cây con V nằm tại vị trí startIdx[V] + k - 1.

Ví dụ chương trình

#include <bits/stdc++.h> 
using namespace std; 

#define N 100005
vector<int> tree[N];
int currentIdx = 0;
vector<int> startIdx, endIdx, 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 (int 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(){
    int 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 nút trong DFS của nút " << v << " là " << findKNodeDfsV(v, k);
    return 0;
}

Kết quả

4-th nút trong DFS của nút 2 là 1