C++ คำถาม DFS ของ Subtree ในต้นไม้

ในปัญหานี้ เราได้รับต้นไม้ไบนารี (Binary Tree) และต้องทำ DFS จากโหนดเฉพาะ โดยถือว่าโหนดที่กำหนดเป็นราก (Root) และทำ DFS จากนั้น

ในต้นไม้ข้างต้น สมมติเราต้องทำ DFS จากโหนด F

ในบทช่วยสอนนี้ เราจะใช้วิธีที่ไม่ธรรมดา (Unorthodox) เพื่อลดความซับซ้อนด้านเวลาอย่างมาก จึงสามารถรันโค้ดสำหรับข้อจำกัดที่สูงกว่าได้

วิธีการ - เราไม่ไปทางตรงไปตรงมา (Naive) คือทำ DFS ทุกครั้งสำหรับทุกโหนด เพราะจะไม่ทำงานได้กับข้อจำกัดสูง เราจึงพยายามใช้วิธีที่ไม่ธรรมดาเพื่อหลีกเลี่ยง TLE (Time Limit Exceeded)

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

#define N 100000 
vector<int> v[N]; 
unordered_map<int, int> mape; 
vector<int> a; 

void dfs(int nodesunder[], int child, int parent){ 
    a.push_back(child); 
    nodesunder[child] = 1; 
    for (auto it : v[child]) { 
        if (it != parent) { 
            dfs(nodesunder, it, child); 
            nodesunder[child] += nodesunder[it]; 
        } 
    } 
} 

void printDFS(int node, int nodesunder[]){ 
    int ind = mape[node]; 
    cout << "The DFS of subtree " << node << ": "; 
    for (int i = ind; i < ind + nodesunder[node]; i++){ 
        cout << a[i] << " "; 
    } 
    cout << endl; 
} 

void addEdgetoGraph(int x, int y){ 
    v[x].push_back(y); 
    v[y].push_back(x); 
} 

void mark(){ 
    int size = a.size(); 
    for (int i = 0; i < size; i++) { 
        mape[a[i]] = i; 
    } 
} 

int main(){ 
    int n = 7; 
    addEdgetoGraph(1, 2); 
    addEdgetoGraph(1, 3); 
    addEdgetoGraph(2, 4); 
    addEdgetoGraph(2, 5); 
    addEdgetoGraph(4, 6); 
    addEdgetoGraph(4, 7); 
    int nodesunder[n + 1]; 
    dfs(nodesunder, 1, 0); 
    mark(); 
    printDFS(2, nodesunder); 
    printDFS(4, nodesunder); 
    return 0; 
}

ผลลัพธ์

The DFS of subtree 2: 2 4 6 7 5
The DFS of subtree 4: 4 6 7

การเข้าใจโค้ด

ในวิธีนี้ เราคำนวณลำดับ DFS ล่วงหน้า (Pre-calculate) และเก็บไว้ใน Vector ตอนที่เราได้ DFS ล่วงหน้าแล้ว เรายังคำนวณจำนวนโหนดภายใต้แต่ละ Subtree เริ่มจากแต่ละโหนด แล้วเราแค่วนลูปจากดัชนีเริ่มต้นของโหนดไปจนถึงจำนวนโหนดใน Subtree ของมัน

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Queries for DFS of a subtree in a tree เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์