C++でDFSを使用してn-aryツリーのすべてのリーフノードを出力します

この問題では、n-aryのエッジを含む2次元配列が与えられます。ここで、edgeはn-aryツリーのエッジを定義します。作成したa-aryツリーのすべてのリーフノードを印刷する必要があります。

n-aryツリー は最大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