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>
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