ในปัญหานี้ เราได้รับอาร์เรย์ 2 มิติที่มีขอบของ n-ary โดยที่ edge กำหนดขอบของแผนผัง n-ary เราต้องพิมพ์ leaf nodes ทั้งหมดของ a-ary tree ที่สร้างขึ้น
ต้นไม้นารี เป็นต้นไม้ที่มีโหนดย่อยสูงสุด n ลูก เช่น โหนดสามารถมีโหนดย่อยได้ 1, 2, ...n โหนด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7 คำอธิบาย − มาสร้างต้นไม้โดยใช้ edge array กัน −
โหนดของต้นไม้นี้คือ 1, 4, 7.
เพื่อแก้ปัญหานี้ เราจะสำรวจต้นไม้โดยใช้ DFS (จะพบโหนดปลายสุดของทรีย่อยทุกต้น) นอกจากนี้ยังมีการทำเครื่องหมายโหนดที่เยี่ยมชมของอาร์เรย์ หากโหนดมีลูก (ถ้าไม่ใช่โหนดปลายสุด) เราจะตั้งค่าสถานะและพิมพ์โหนดที่ไม่มีโหนดย่อย
ตัวอย่าง
โปรแกรมนี้แสดงการใช้งานโซลูชันของเรา -
#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;
} ผลลัพธ์
Leaf nodes of the tree are − 4 5 8 7
