Dado un árbol genérico tal que cada Node tiene un valor asociado, la tarea es encontrar el mayor número de Nodes conectados que tengan el mismo valor en el árbol. Dos Nodes están conectados si un Node es hijo de otro Node.
Ejemplo:
Entrada: Árbol en la imagen de abajo
Salida: 4 Explicación: El grupo más grande de Nodes conectados tiene el valor 3 con un número de Nodes igual a 4.
Entrada: Árbol en la imagen de abajo
Salida: 2
Enfoque: El problema dado se puede resolver utilizando el recorrido posterior al pedido . La idea es verificar si el Node secundario tiene el mismo valor que su Node principal y agregar 1 a la respuesta devuelta por el Node secundario. Se pueden seguir los siguientes pasos para resolver el problema:
- Aplique el recorrido posterior al pedido en el árbol N-ario:
- Si la raíz no tiene hijos, devuelve 1 al padre
- Agregue todas las respuestas devueltas por los Nodes secundarios cuyo valor sea el mismo que el Node actual
- Actualizar el número máximo de Nodes conectados
- Devuelve el número máximo de Nodes conectados como respuesta
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
vector<Node*> children;
int val;
// constructor
Node(int v)
{
val = v;
children = {};
}
};
// Post order traversal function
// to calculate the largest group
// of connected nodes
int postOrder(Node* root, int maxi[])
{
// If the current node has no
// children then return 1
if (root->children.size() == 0)
return 1;
// Initialize a variable sum to
// calculate largest group connected
// to current node with same value
// as current node
int sum = 1;
// Iterate through all neighbors
for (Node* child : root->children) {
// Get the value from children
int nodes = postOrder(child, maxi);
// If child node value is same as
// current node then add the
// returned value to sum
if (child->val == root->val)
sum += nodes;
}
// Update maximum connected
// nodes if sum is greater
maxi[0] = max(maxi[0], sum);
// Return the connected group
// to the current node
return sum;
}
// Function to find the largest
// number of nodes in a tree
int largestGroup(Node* root)
{
// Base case
if (root == NULL)
return 0;
// Initialize a variable max
// to calculate largest group
int maxi[1];
// Post-order traversal
postOrder(root, maxi);
// Return the answer
return maxi[0];
}
// Driver code
int main()
{
// Initialize the tree
Node* three1 = new Node(3);
Node* three2 = new Node(3);
Node* three3 = new Node(3);
Node* three4 = new Node(3);
Node* two1 = new Node(2);
Node* two2 = new Node(2);
Node* two3 = new Node(2);
Node* two4 = new Node(2);
Node* four1 = new Node(4);
Node* four2 = new Node(4);
Node* four3 = new Node(4);
Node* one1 = new Node(1);
Node* one2 = new Node(1);
Node* one3 = new Node(1);
Node* one4 = new Node(1);
three2->children.push_back(two1);
three2->children.push_back(three1);
three2->children.push_back(three3);
four1->children.push_back(four2);
four1->children.push_back(four3);
two2->children.push_back(one1);
two2->children.push_back(one2);
two2->children.push_back(two3);
one3->children.push_back(one4);
one3->children.push_back(two4);
three4->children.push_back(three2);
three4->children.push_back(four1);
three4->children.push_back(two2);
three4->children.push_back(one3);
// Call the function
// and print the result
cout << (largestGroup(three4));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
static class Node {
List<Node> children;
int val;
// constructor
public Node(int val)
{
this.val = val;
children = new ArrayList<>();
}
}
// Function to find the largest
// number of nodes in a tree
public static int largestGroup(Node root)
{
// Base case
if (root == null)
return 0;
// Initialize a variable max
// to calculate largest group
int[] max = new int[1];
// Post-order traversal
postOrder(root, max);
// Return the answer
return max[0];
}
// Post order traversal function
// to calculate the largest group
// of connected nodes
public static int postOrder(
Node root, int[] max)
{
// If the current node has no
// children then return 1
if (root.children.size() == 0)
return 1;
// Initialize a variable sum to
// calculate largest group connected
// to current node with same value
// as current node
int sum = 1;
// Iterate through all neighbors
for (Node child : root.children) {
// Get the value from children
int nodes = postOrder(child, max);
// If child node value is same as
// current node then add the
// returned value to sum
if (child.val == root.val)
sum += nodes;
}
// Update maximum connected
// nodes if sum is greater
max[0] = Math.max(max[0], sum);
// Return the connected group
// to the current node
return sum;
}
// Driver code
public static void main(String[] args)
{
// Initialize the tree
Node three1 = new Node(3);
Node three2 = new Node(3);
Node three3 = new Node(3);
Node three4 = new Node(3);
Node two1 = new Node(2);
Node two2 = new Node(2);
Node two3 = new Node(2);
Node two4 = new Node(2);
Node four1 = new Node(4);
Node four2 = new Node(4);
Node four3 = new Node(4);
Node one1 = new Node(1);
Node one2 = new Node(1);
Node one3 = new Node(1);
Node one4 = new Node(1);
three2.children.add(two1);
three2.children.add(three1);
three2.children.add(three3);
four1.children.add(four2);
four1.children.add(four3);
two2.children.add(one1);
two2.children.add(one2);
two2.children.add(two3);
one3.children.add(one4);
one3.children.add(two4);
three4.children.add(three2);
three4.children.add(four1);
three4.children.add(two2);
three4.children.add(one3);
// Call the function
// and print the result
System.out.println(
largestGroup(three4));
}
}
Python3
# Python code for the above approach class Node: # constructor def __init__(self, v): self.val = v; self.children = []; # Post order traversal function # to calculate the largest group # of connected nodes def postOrder(root, maxi): # If the current node has no # children then return 1 if (len(root.children) == 0): return 1; # Initialize a variable sum to # calculate largest group connected # to current node with same value # as current node sum = 1; # Iterate through all neighbors for child in root.children: # Get the value from children nodes = postOrder(child, maxi); # If child node value is same as # current node then add the # returned value to sum if (child.val == root.val): sum += nodes; # Update maximum connected # nodes if sum is greater maxi[0] = max(maxi[0], sum); # Return the connected group # to the current node return sum; # Function to find the largest # number of nodes in a tree def largestGroup(root): # Base case if (root == None): return 0; # Initialize a variable max # to calculate largest group maxi = [0]; # Post-order traversal postOrder(root, maxi); # Return the answer return maxi[0]; # Driver code # Initialize the tree three1 = Node(3); three2 = Node(3); three3 = Node(3); three4 = Node(3); two1 = Node(2); two2 = Node(2); two3 = Node(2); two4 = Node(2); four1 = Node(4); four2 = Node(4); four3 = Node(4); one1 = Node(1); one2 = Node(1); one3 = Node(1); one4 = Node(1); three2.children.append(two1); three2.children.append(three1); three2.children.append(three3); four1.children.append(four2); four1.children.append(four3); two2.children.append(one1); two2.children.append(one2); two2.children.append(two3); one3.children.append(one4); one3.children.append(two4); three4.children.append(three2); three4.children.append(four1); three4.children.append(two2); three4.children.append(one3); # Call the function # and print the result print((largestGroup(three4))); # This code is contributed by gfgking
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
// Class representing a Node of an N-ary tree
public class Node
{
public int val;
public List<Node> children;
// Constructor to create a Node
public Node(int vall)
{
val = vall;
children = new List<Node>();
}
}
class GFG {
// Function to find the largest
// number of nodes in a tree
public static int largestGroup(Node root)
{
// Base case
if (root == null)
return 0;
// Initialize a variable max
// to calculate largest group
int[] max = new int[1];
// Post-order traversal
postOrder(root, max);
// Return the answer
return max[0];
}
// Post order traversal function
// to calculate the largest group
// of connected nodes
public static int postOrder(
Node root, int[] max)
{
// If the current node has no
// children then return 1
if (root.children.Count == 0)
return 1;
// Initialize a variable sum to
// calculate largest group connected
// to current node with same value
// as current node
int sum = 1;
// Iterate through all neighbors
foreach (Node child in root.children) {
// Get the value from children
int nodes = postOrder(child, max);
// If child node value is same as
// current node then Add the
// returned value to sum
if (child.val == root.val)
sum += nodes;
}
// Update maximum connected
// nodes if sum is greater
max[0] = Math.Max(max[0], sum);
// Return the connected group
// to the current node
return sum;
}
// Driver code
static public void Main (){
// Initialize the tree
Node three1 = new Node(3);
Node three2 = new Node(3);
Node three3 = new Node(3);
Node three4 = new Node(3);
Node two1 = new Node(2);
Node two2 = new Node(2);
Node two3 = new Node(2);
Node two4 = new Node(2);
Node four1 = new Node(4);
Node four2 = new Node(4);
Node four3 = new Node(4);
Node one1 = new Node(1);
Node one2 = new Node(1);
Node one3 = new Node(1);
Node one4 = new Node(1);
three2.children.Add(two1);
three2.children.Add(three1);
three2.children.Add(three3);
four1.children.Add(four2);
four1.children.Add(four3);
two2.children.Add(one1);
two2.children.Add(one2);
two2.children.Add(two3);
one3.children.Add(one4);
one3.children.Add(two4);
three4.children.Add(three2);
three4.children.Add(four1);
three4.children.Add(two2);
three4.children.Add(one3);
// Call the function
// and print the result
Console.WriteLine(
largestGroup(three4));
}
}
// This code is contributed
// by Shubham Singh
Javascript
<script>
// Javascript code for the above approach
class Node {
// constructor
constructor(v) {
this.val = v;
this.children = [];
}
};
// Post order traversal function
// to calculate the largest group
// of connected nodes
function postOrder(root, maxi) {
// If the current node has no
// children then return 1
if (root.children.length == 0)
return 1;
// Initialize a variable sum to
// calculate largest group connected
// to current node with same value
// as current node
let sum = 1;
// Iterate through all neighbors
for (child of root.children) {
// Get the value from children
let nodes = postOrder(child, maxi);
// If child node value is same as
// current node then add the
// returned value to sum
if (child.val == root.val)
sum += nodes;
}
// Update maximum connected
// nodes if sum is greater
maxi[0] = Math.max(maxi[0], sum);
// Return the connected group
// to the current node
return sum;
}
// Function to find the largest
// number of nodes in a tree
function largestGroup(root) {
// Base case
if (root == null)
return 0;
// Initialize a variable max
// to calculate largest group
let maxi = [0];
// Post-order traversal
postOrder(root, maxi);
// Return the answer
return maxi[0];
}
// Driver code
// Initialize the tree
let three1 = new Node(3);
let three2 = new Node(3);
let three3 = new Node(3);
let three4 = new Node(3);
let two1 = new Node(2);
let two2 = new Node(2);
let two3 = new Node(2);
let two4 = new Node(2);
let four1 = new Node(4);
let four2 = new Node(4);
let four3 = new Node(4);
let one1 = new Node(1);
let one2 = new Node(1);
let one3 = new Node(1);
let one4 = new Node(1);
three2.children.push(two1);
three2.children.push(three1);
three2.children.push(three3);
four1.children.push(four2);
four1.children.push(four3);
two2.children.push(one1);
two2.children.push(one2);
two2.children.push(two3);
one3.children.push(one4);
one3.children.push(two4);
three4.children.push(three2);
three4.children.push(four1);
three4.children.push(two2);
three4.children.push(one3);
// Call the function
// and print the result
document.write((largestGroup(three4)));
// This code is contributed by gfgking
</script>
Producción:
4
Complejidad de Tiempo: O(N), donde N es el número de Nodes en el árbol
Espacio Auxiliar: O(H), H es la altura del árbol
Publicación traducida automáticamente
Artículo escrito por shahid24sunny17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA