이 문제에서는 n차 트리의 가장자리를 정의하는 edge에서 n차의 가장자리를 포함하는 2차원 배열이 제공됩니다. 생성된 aary 트리의 모든 리프 노드를 인쇄해야 합니다.
n항 트리 최대 n개의 자식이 있는 트리입니다. 즉, 노드는 1, 2, ...n개의 자식 노드를 가질 수 있습니다.
문제를 이해하기 위한 예를 살펴보겠습니다 -
Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7 설명 − 에지 배열을 사용하여 트리를 생성해 보겠습니다. −
이 트리의 리프 노드는 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