หา K-th Node ใน DFS Traversal ของ Subtree ใน Tree ใน C++

ในปัญหานี้ เราได้รับ Tree ขนาด N, Node V, และ K งานคือหา K-th node ใน DFS traversal ของ subtree ที่ rooted ที่ V

ตัวอย่าง

V = 2, k = 3 (1-indexed) Output: 4

DFS from 2: {2, 3, 5, 6, 7} → 3rd = 5 (โค้ดตัวอย่างใช้ 0-indexed ให้ 4)

วิธีการแก้ปัญหา: Pre-compute DFS Order

1. DFS ทั้ง tree บันทึกลำดับใน vector dfsOrder
2. บันทึก startIdx[v] และ endIdx[v] สำหรับแต่ละ node
3. K-th node ใน subtree V = dfsOrder[startIdx[V] + k - 1] (ถ้าในช่วง)

ตัวอย่างโค้ด

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

#define N 100005
vector tree[N];
vector startIdx, endIdx, dfsOrder;
int currentIdx = 0;

void addEdge(int u, int v) {
    tree[u].push_back(v);
    tree[v].push_back(u);
}

void dfs(int u, int parent) {
    dfsOrder[currentIdx] = u;
    startIdx[u] = currentIdx++;
    for (int v : tree[u])
        if (v != parent) dfs(v, u);
    endIdx[u] = currentIdx - 1;
}

int findKthNode(int v, int k) {
    k = k + startIdx[v] - 1; // 1-indexed k
    if (k <= endIdx[v]) return dfsOrder[k];
    return -1;
}

int main() {
    // build tree...
    dfs(5, 0);
    cout << findKthNode(2, 4); // 1
    return 0;
}

ผลลัพธ์

4-th node in DFS traversal of node 2 is 1