Dado un árbol binario que consta de N Nodes enraizados en 1 , un número entero K y una array arr[] que consta de valores asignados a cada Node, la tarea es contar el número de rutas de raíz a hoja que tienen exactamente K Nodes distintos en el binario dado. Árbol.
Ejemplos:
Entrada: N = 3, Edges[][] = {{1, 2}, {1, 3}}, arr[] = {3, 3, 2}, K = 2, A continuación se muestra el árbol dado:
Salida: 1
Explicación:
existe solo 1 ruta distinta, es decir, la ruta 1 -> 3 contiene 2 Nodes distintos.
Por lo tanto, la respuesta es 1.Entrada: N = 7, Bordes[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}}, arr[] = {2, 2, 2, 2, 3, 5, 2}, K = 1, a continuación se muestra el árbol dado:
Salida: 2
Explicación:
Solo existen 2 rutas distintas que contienen 1 Node distinto:
1) Rutas 1 -> 2 -> 4,
2) Rutas 1 -> 3 -> 7
Por lo tanto, la respuesta es 2.
Enfoque ingenuo: el enfoque más simple es generar todas las rutas posibles desde la raíz hasta los Nodes hoja y, para cada ruta, verificar si contiene K Nodes distintos o no. Finalmente, imprima el recuento de dichos caminos.
Complejidad temporal: O(N * H 2 ), donde H denota la altura del árbol.
Espacio Auxiliar: O(N);
Enfoque eficiente: la idea es usar Preorder Traversal y un mapa para contar el Node distinto en la ruta desde la raíz hasta el Node actual. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable different_nodes como 0 para almacenar el recuento del Node distinto desde la raíz hasta el Node actual y ans como 0 para almacenar el total de rutas distintas de la raíz a la hoja que tienen K Nodes distintos.
- Realice Preorder Traversal en el árbol binario dado y almacene el recuento del Node distinto desde la raíz hasta el Node actual en el mapa M .
- Cada vez que aparece un Node por primera vez en una ruta, aumente el recuento de Nodes distintos en 1 .
- Si el recuento de Nodes distintos en una ruta es mayor que K , regrese al Node principal del Node actual.
- De lo contrario, continúe visitando los hijos del Node actual incrementando la frecuencia del valor del Node actual en 1 .
- En el paso anterior, incremente ans en 1 si el recuento de Nodes distintos en esa ruta de raíz a hoja es exactamente igual a K .
- Después de los pasos anteriores, imprima el valor de ans como el conteo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a Tree Node struct Node { int key; Node *left, *right; }; // Function to create new tree node Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } // Function to count all root to leaf // paths having K distinct nodes void findkDistinctNodePaths( Node* root, unordered_map<int, int> freq, int distinct_nodes, int k, int& ans) { // If current node is null if (root == NULL) return; // Update count of distinct nodes if (freq[root->key] == 0) distinct_nodes++; // If count > k then return to // the parent node if (distinct_nodes > k) return; // Update frequency of current node freq[root->key]++; // Go to the left subtree findkDistinctNodePaths(root->left, freq, distinct_nodes, k, ans); // Go to the right subtree findkDistinctNodePaths(root->right, freq, distinct_nodes, k, ans); // If current node is leaf node if (root->left == NULL && root->right == NULL) { // If count of distinct node // is same as K, increment ans if (distinct_nodes == k) ans++; } } // Function to find count of root to // leaf paths having K distinct node void printkDistinctNodePaths(Node* root, int k) { // Initialize unordered map unordered_map<int, int> freq; // Stores count of distinct node int distinct_nodes = 0; // Stores total count of nodes int ans = 0; // Perform Preorder Traversal findkDistinctNodePaths(root, freq, distinct_nodes, k, ans); // Print the final count cout << ans; } // Driver Code int main() { /* 2 / \ / \ 1 3 / \ / \ / \ / \ 4 2 -5 3 */ // Given Binary Tree Node* root = newNode(2); root->left = newNode(1); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(2); root->right->left = newNode(-5); root->right->right = newNode(3); // Given K int K = 2; // Function Call printkDistinctNodePaths(root, K); return 0; }
Java
// Java program for the // above approach import java.util.*; class GFG{ // Structure of a // Tree Node static class Node { int key; Node left, right; }; static int ans; // Function to create // new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return temp; } // Function to count all root // to leaf paths having K // distinct nodes static void findkDistinctNodePaths(Node root, HashMap<Integer, Integer> freq, int distinct_nodes, int k) { // If current node is null if (root == null) return; // Update count of distinct nodes if (!freq.containsKey(root.key)) distinct_nodes++; // If count > k then return // to the parent node if (distinct_nodes > k) return; // Update frequency of // current node if(freq.containsKey(root.key)) { freq.put(root.key, freq.get(root.key) + 1); } else { freq.put(root.key, 1); } // Go to the left subtree findkDistinctNodePaths(root.left, freq, distinct_nodes, k); // Go to the right subtree findkDistinctNodePaths(root.right, freq, distinct_nodes, k); // If current node is // leaf node if (root.left == null && root.right == null) { // If count of distinct node // is same as K, increment ans if (distinct_nodes == k) ans++; } } // Function to find count of root to // leaf paths having K distinct node static void printkDistinctNodePaths(Node root, int k) { // Initialize unordered map HashMap<Integer, Integer> freq = new HashMap<>(); // Stores count of // distinct node int distinct_nodes = 0; // Stores total // count of nodes ans = 0; // Perform Preorder Traversal findkDistinctNodePaths(root, freq, distinct_nodes, k); // Print the final count System.out.print(ans); } // Driver Code public static void main(String[] args) { /* 2 / \ / \ 1 3 / \ / \ / \ / \ 4 2 -5 3 */ // Given Binary Tree Node root = newNode(2); root.left = newNode(1); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(2); root.right.left = newNode(-5); root.right.right = newNode(3); // Given K int K = 2; // Function Call printkDistinctNodePaths(root, K); } } // This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Structure of a Tree Node class newNode: def __init__(self, key): self.key = key self.left = None self.right = None ans = 0 # Function to count all root to leaf # paths having K distinct nodes def findkDistinctNodePaths(root, freq, distinct_nodes, k): global ans # If current node is None if (root == None): return # Update count of distinct nodes if (root.key not in freq): distinct_nodes += 1 # If count > k then return to # the parent node if (distinct_nodes > k): return # Update frequency of current node if (root.key in freq): freq[root.key] += 1 else: freq[root.key] = freq.get(root.key, 0) + 1 # Go to the left subtree findkDistinctNodePaths(root.left, freq, distinct_nodes, k) # Go to the right subtree findkDistinctNodePaths(root.right, freq, distinct_nodes, k) # If current node is leaf node if (root.left == None and root.right == None): # If count of distinct node # is same as K, increment ans if (distinct_nodes == k): ans += 1 # Function to find count of root to # leaf paths having K distinct node def printkDistinctNodePaths(root, k): global ans # Initialize unordered map freq = {} # Stores count of distinct node distinct_nodes = 0 # Perform Preorder Traversal findkDistinctNodePaths(root, freq, distinct_nodes, k) # Print the final count print(ans) # Driver Code if __name__ == '__main__': ''' 2 / \ / \ 1 3 / \ / \ / \ / \ 4 2 -5 3 ''' # Given Binary Tree root = newNode(2) root.left = newNode(1) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(2) root.right.left = newNode(-5) root.right.right = newNode(3) # Given K K = 2 # Function Call printkDistinctNodePaths(root, K) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Structure of a // Tree Node public class Node { public int key; public Node left, right; }; static int ans; // Function to create // new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return temp; } // Function to count all root // to leaf paths having K // distinct nodes static void findkDistinctNodePaths(Node root, Dictionary<int, int> freq, int distinct_nodes, int k) { // If current node is null if (root == null) return; // Update count of distinct nodes if (!freq.ContainsKey(root.key)) distinct_nodes++; // If count > k then return // to the parent node if (distinct_nodes > k) return; // Update frequency of // current node if (freq.ContainsKey(root.key)) { freq[root.key] = freq[root.key] + 1; } else { freq.Add(root.key, 1); } // Go to the left subtree findkDistinctNodePaths(root.left, freq, distinct_nodes, k); // Go to the right subtree findkDistinctNodePaths(root.right, freq, distinct_nodes, k); // If current node is // leaf node if (root.left == null && root.right == null) { // If count of distinct node // is same as K, increment ans if (distinct_nodes == k) ans++; } } // Function to find count of root to // leaf paths having K distinct node static void printkDistinctNodePaths(Node root, int k) { // Initialize unordered map Dictionary<int, int> freq = new Dictionary<int, int>(); // Stores count of // distinct node int distinct_nodes = 0; // Stores total // count of nodes ans = 0; // Perform Preorder Traversal findkDistinctNodePaths(root, freq, distinct_nodes, k); // Print the readonly count Console.Write(ans); } // Driver Code public static void Main(String[] args) { /* 2 / \ / \ 1 3 / \ / \ / \ / \ 4 2 -5 3 */ // Given Binary Tree Node root = newNode(2); root.left = newNode(1); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(2); root.right.left = newNode(-5); root.right.right = newNode(3); // Given K int K = 2; // Function Call printkDistinctNodePaths(root, K); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program for the above approach // Structure of tree node class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } let ans; // Function to create // new tree node function newNode(key) { let temp = new Node(key); return temp; } // Function to count all root // to leaf paths having K // distinct nodes function findkDistinctNodePaths(root, freq, distinct_nodes, k) { // If current node is null if (root == null) return; // Update count of distinct nodes if (!freq.has(root.key)) distinct_nodes++; // If count > k then return // to the parent node if (distinct_nodes > k) return; // Update frequency of // current node if (freq.has(root.key)) { freq.set(root.key, freq.get(root.key) + 1); } else { freq.set(root.key, 1); } // Go to the left subtree findkDistinctNodePaths(root.left, freq, distinct_nodes, k); // Go to the right subtree findkDistinctNodePaths(root.right, freq, distinct_nodes, k); // If current node is // leaf node if (root.left == null && root.right == null) { // If count of distinct node // is same as K, increment ans if (distinct_nodes == k) ans++; } } // Function to find count of root to // leaf paths having K distinct node function printkDistinctNodePaths(root, k) { // Initialize unordered map let freq = new Map(); // Stores count of // distinct node let distinct_nodes = 0; // Stores total // count of nodes ans = 0; // Perform Preorder Traversal findkDistinctNodePaths(root, freq, distinct_nodes, k); // Print the final count document.write(ans); } // Driver code /* 2 / \ / \ 1 3 / \ / \ / \ / \ 4 2 -5 3 */ // Given Binary Tree let root = newNode(2); root.left = newNode(1); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(2); root.right.left = newNode(-5); root.right.right = newNode(3); // Given K let K = 2; // Function Call printkDistinctNodePaths(root, K); // This code is contributed by suresh07 </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA