พิมพ์ Leaf Nodes ของ N-ary Tree ด้วย DFS ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ 2D เก็บ Edge ของ N-ary Tree ต้องพิมพ์ Leaf Nodes ทั้งหมด

N-ary Tree คืออะไร?

ต้นไม้ที่โหนดแต่ละตัวมีลูกได้สูงสุด n ตัว (1, 2, ..., n ลูก)

ตัวอย่าง

Input: edges[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7

วิธีแก้ปัญหา (DFS)

1. สร้าง Adjacency List จาก Edge list
2. DFS จากโหนดราก (1) พร้อมส่ง parent parameter
3. ถ้าโหนดไม่มีลูกนอกจาก parent → เป็น Leaf → พิมพ์

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

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

void DFS(list<int> t[], int node, int parent) {
    int flag = 0;
    for (auto ir : t[node]) {
        if (ir != parent) {
            flag = 1;
            DFS(t, ir, node);
        }
    }
    if (flag == 0)
        cout << node << "\t";
}

int main() {
    list<int> t[1005];
    pair<int, int> edges[] = {
        { 1, 2 }, { 1, 3 }, { 2, 4 },
        { 3, 5 }, { 3, 6 }, { 3, 7 }, { 6, 8 }
    };
    int cnt = sizeof(edges) / sizeof(edges[0]);
    int node = cnt + 1;
    for (int i = 0; i < cnt; i++) {
        t[edges[i].first].push_back(edges[i].second);
        t[edges[i].second].push_back(edges[i].first);
    }
    cout << "Leaf nodes of the tree are:\n";
    DFS(t, 1, 0);
    return 0;
}

ผลลัพธ์ (Output)

Leaf nodes of the tree are:
4 5 8 7