Dado un árbol N-ario , imprima el número de Nodes hoja en el subárbol de cada Node.
Ejemplos :
Input:
1
/ \
2 3
/ | \
4 5 6
Output:
The node 1 has 4 leaf nodes
The node 2 has 1 leaf nodes
The node 3 has 3 leaf nodes
The node 4 has 1 leaf nodes
The node 5 has 1 leaf nodes
The node 6 has 1 leaf nodes
Enfoque : la idea es realizar un recorrido DFS en el árbol dado y para cada Node mantener una hoja de array [] para almacenar el recuento de Nodes de hoja en el subárbol debajo de él.
Ahora, mientras se repite hacia abajo en el árbol, si se encuentra un Node de hoja, establezca su valor de hoja[i] en 1 y regrese en dirección ascendente. Ahora, cada vez que regrese de la llamada de función hacia arriba, agregue los Nodes de hoja del Node debajo.
Una vez que se complete el recorrido DFS, tendremos el recuento de Nodes de hoja en la array leaf[].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the number of
// leaf nodes of every node
#include <bits/stdc++.h>
using namespace std;
// Function to insert edges of tree
void insert(int x, int y, vector<int> adjacency[])
{
adjacency[x].push_back(y);
}
// Function to run DFS on a tree
void dfs(int node, int leaf[], int vis[],
vector<int> adjacency[])
{
leaf[node] = 0;
vis[node] = 1;
// iterate on all the nodes
// connected to node
for (auto it : adjacency[node]) {
// If not visited
if (!vis[it]) {
dfs(it, leaf, vis, adjacency);
leaf[node] += leaf[it];
}
}
if (!adjacency[node].size())
leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
void printLeaf(int n, int leaf[])
{
// Function to print leaf nodes
for (int i = 1; i <= n; i++) {
cout << "The node " << i << " has "
<< leaf[i] << " leaf nodes\n";
}
}
// Driver Code
int main()
{
// Given N-ary Tree
/* 1
/ \
2 3
/ | \
4 5 6 */
int N = 6; // no of nodes
vector<int> adjacency[N + 1]; // adjacency list for tree
insert(1, 2, adjacency);
insert(1, 3, adjacency);
insert(3, 4, adjacency);
insert(3, 5, adjacency);
insert(3, 6, adjacency);
int leaf[N + 1]; // Store count of leaf in subtree of i
int vis[N + 1] = { 0 }; // mark nodes visited
dfs(1, leaf, vis, adjacency);
printLeaf(N, leaf);
return 0;
}
Java
// Java program to print the number of
// leaf nodes of every node
import java.util.*;
class GFG
{
static Vector<Vector<Integer>> adjacency = new
Vector<Vector<Integer>>();
// Function to insert edges of tree
static void insert(int x, int y)
{
adjacency.get(x).add(y);
}
// Function to run DFS on a tree
static void dfs(int node, int leaf[], int vis[])
{
leaf[node] = 0;
vis[node] = 1;
// iterate on all the nodes
// connected to node
for (int i = 0; i < adjacency.get(node).size(); i++)
{
int it = adjacency.get(node).get(i);
// If not visited
if (vis[it] == 0)
{
dfs(it, leaf, vis);
leaf[node] += leaf[it];
}
}
if (adjacency.get(node).size() == 0)
leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
static void printLeaf(int n, int leaf[])
{
// Function to print leaf nodes
for (int i = 1; i <= n; i++)
{
System.out.print( "The node " + i + " has " +
leaf[i] + " leaf nodes\n");
}
}
// Driver Code
public static void main(String args[])
{
// Given N-ary Tree
/* 1
/ \
2 3
/ | \
4 5 6 */
int N = 6; // no of nodes
for(int i = 0; i <= N; i++)
adjacency.add(new Vector<Integer>());
insert(1, 2);
insert(1, 3);
insert(3, 4);
insert(3, 5);
insert(3, 6);
// Store count of leaf in subtree of i
int leaf[] = new int[N + 1];
// mark nodes visited
int vis[] = new int[N + 1] ;
dfs(1, leaf, vis);
printLeaf(N, leaf);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print the number of
# leaf nodes of every node
adjacency = [[] for i in range(100)]
# Function to insert edges of tree
def insert(x, y):
adjacency[x].append(y)
# Function to run DFS on a tree
def dfs(node, leaf, vis):
leaf[node] = 0
vis[node] = 1
# iterate on all the nodes
# connected to node
for it in adjacency[node]:
# If not visited
if (vis[it] == False):
dfs(it, leaf, vis)
leaf[node] += leaf[it]
if (len(adjacency[node]) == 0):
leaf[node] = 1
# Function to print number of
# leaf nodes of a node
def printLeaf(n, leaf):
# Function to print leaf nodes
for i in range(1, n + 1):
print("The node", i, "has",
leaf[i], "leaf nodes")
# Driver Code
# Given N-ary Tree
'''
/* 1
/ \
2 3
/ | \
4 5 6 '''
N = 6 # no of nodes
# adjacency list for tree
insert(1, 2)
insert(1, 3)
insert(3, 4)
insert(3, 5)
insert(3, 6)
# Store count of leaf in subtree of i
leaf = [0 for i in range(N + 1)]
# mark nodes visited
vis = [0 for i in range(N + 1)]
dfs(1, leaf, vis)
printLeaf(N, leaf)
# This code is contributed by Mohit Kumar
C#
// C# program to print the number of
// leaf nodes of every node
using System;
using System.Collections.Generic;
class GFG
{
static List<List<int>> adjacency = new
List<List<int>>();
// Function to insert edges of tree
static void insert(int x, int y)
{
adjacency[x].Add(y);
}
// Function to run DFS on a tree
static void dfs(int node, int []leaf, int []vis)
{
leaf[node] = 0;
vis[node] = 1;
// iterate on all the nodes
// connected to node
for (int i = 0; i < adjacency[node].Count; i++)
{
int it = adjacency[node][i];
// If not visited
if (vis[it] == 0)
{
dfs(it, leaf, vis);
leaf[node] += leaf[it];
}
}
if (adjacency[node].Count == 0)
leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
static void printLeaf(int n, int []leaf)
{
// Function to print leaf nodes
for (int i = 1; i <= n; i++)
{
Console.Write( "The node " + i + " has " +
leaf[i] + " leaf nodes\n");
}
}
// Driver Code
public static void Main(String []args)
{
// Given N-ary Tree
/* 1
/ \
2 3
/ | \
4 5 6 */
int N = 6; // no of nodes
for(int i = 0; i <= N; i++)
adjacency.Add(new List<int>());
insert(1, 2);
insert(1, 3);
insert(3, 4);
insert(3, 5);
insert(3, 6);
// Store count of leaf in subtree of i
int []leaf = new int[N + 1];
// mark nodes visited
int []vis = new int[N + 1] ;
dfs(1, leaf, vis);
printLeaf(N, leaf);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to print the number of
// leaf nodes of every node
let adjacency = [];
// Function to insert edges of tree
function insert(x,y)
{
adjacency[x].push(y);
}
// Function to run DFS on a tree
function dfs(node,leaf,vis)
{
leaf[node] = 0;
vis[node] = 1;
// iterate on all the nodes
// connected to node
for (let i = 0; i < adjacency[node].length; i++)
{
let it = adjacency[node][i];
// If not visited
if (vis[it] == 0)
{
dfs(it, leaf, vis);
leaf[node] += leaf[it];
}
}
if (adjacency[node].length == 0)
leaf[node] = 1;
}
// Function to print number of
// leaf nodes of a node
function printLeaf(n,leaf)
{
// Function to print leaf nodes
for (let i = 1; i <= n; i++)
{
document.write( "The node " + i + " has " +
leaf[i] + " leaf nodes<br>");
}
}
// Driver Code
// Given N-ary Tree
/* 1
/ \
2 3
/ | \
4 5 6 */
let N = 6; // no of nodes
for(let i = 0; i <= N; i++)
adjacency.push([]);
insert(1, 2);
insert(1, 3);
insert(3, 4);
insert(3, 5);
insert(3, 6);
// Store count of leaf in subtree of i
let leaf = new Array(N + 1);
for(let i=0;i<leaf.length;i++)
{
leaf[i]=0;
}
// mark nodes visited
let vis = new Array(N + 1) ;
for(let i=0;i<vis.length;i++)
{
vis[i]=0;
}
dfs(1, leaf, vis);
printLeaf(N, leaf);
// This code is contributed by patel2127
</script>
Producción:
The node 1 has 4 leaf nodes The node 2 has 1 leaf nodes The node 3 has 3 leaf nodes The node 4 has 1 leaf nodes The node 5 has 1 leaf nodes The node 6 has 1 leaf nodes
Complejidad de tiempo: O (N), ya que estamos atravesando el árbol usando DFS (recursión), donde N es el número de Nodes en el árbol.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra para el árbol. Donde N es el número de Nodes en el árbol.