Dado un árbol binario que consta de N Nodes, valorados de 1 a N , con raíz en el Node 1 , la tarea para cada Node es contar el número de ancestros con un valor menor que el del Node actual.
Ejemplos:
Entrada: a continuación se muestra el árbol dado:
1
/ \
4 5
/ /\
6 3 2
Salida: 0 1 1 1 1 2
Explicación:
dado que el Node 1 es el Node raíz, no tiene ancestros.
Ancestros del Node 2: {1, 5}. El número de antepasados que tienen un valor menor que 2 es 1.
Antepasados del Node 3: {1, 5}. El número de antepasados que tienen un valor menor que 3 es 1.
Antepasados del Node 4: {1}. El número de antepasados que tienen un valor menor que 4 es 1.
Antepasados del Node 5: {1}. El número de antepasados que tienen un valor menor que 5 es 1.
Antepasados del Node 6: {1, 4}. El número de antepasados que tienen un valor menor que 6 es 2.Entrada: a continuación se muestra el árbol dado:
1
/ \
3 2
\
4
Salida: 0 1 1 2
Explicación:
el Node 1 no tiene antepasados.
Ancestros del Node 2: {1}. El número de antepasados que tienen un valor menor que 2 es 1.
Antepasados del Node 3: {1}. El número de antepasados que tienen un valor menor que 3 es 1.
Antepasados del Node 4: {1, 2}. El número de antepasados que tienen un valor menor que 4 es 2.
Enfoque: la idea es realizar un recorrido DFS desde el Node raíz del árbol y almacenar el padre inmediato de cada Node en una array. Luego itere sobre cada Node y usando la array principal, compare su valor con todos sus ancestros. Finalmente, imprime el resultado.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos par[] de tamaño N , con -1 , para almacenar el padre inmediato de cada Node.
- Realice el recorrido DFS desde el Node raíz y realice los siguientes pasos:
- Actualiza el padre del Node actual.
- Llama recursivamente a los hijos del Node actual.
- Ahora, itere sobre el rango [1, N] usando una variable i y realice los siguientes pasos:
- Almacene el Node actual en una variable, digamos Node .
- Iterar mientras par[node] no es igual a -1 :
- Si par[node] es menor que i , entonces incremente cnt en 1 .
- Actualice el Node como par[node] .
- Después de completar los pasos anteriores, imprima el valor de cnt como el valor del Node actual.
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; // Function to add an edge // between nodes u and v void add_edge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Function to perform the DFS Traversal // and store parent of each node void dfs(vector<int>& parent, vector<int> adj[], int u, int par = -1) { // Store the immediate parent parent[u] = par; // Traverse the children of // the current node for (auto child : adj[u]) { // Recursively call for // function dfs for the // child node if (child != par) dfs(parent, adj, child, u); } } // Function to count the number of // ancestors with values smaller // than that of the current node void countSmallerAncestors( vector<int> adj[], int n) { // Stores the parent of each node vector<int> parent(int(1e5), 0); // Perform the DFS Traversal dfs(parent, adj, 1); // Traverse all the nodes for (int i = 1; i <= n; i++) { int node = i; // Store the number of ancestors // smaller than node int cnt = 0; // Loop until parent[node] != -1 while (parent[node] != -1) { // If the condition satisfies, // increment cnt by 1 if (parent[node] < i) cnt += 1; node = parent[node]; } // Print the required result // for the current node cout << cnt << " "; } } // Driver Code int main() { int N = 6; vector<int> adj[int(1e5)]; // Tree Formation add_edge(adj, 1, 5); add_edge(adj, 1, 4); add_edge(adj, 4, 6); add_edge(adj, 5, 3); add_edge(adj, 5, 2); countSmallerAncestors(adj, N); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to add an edge // between nodes u and v static void add_edge(ArrayList<ArrayList<Integer>> adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // Function to perform the DFS Traversal // and store parent of each node static void dfs(ArrayList<Integer> parent, ArrayList<ArrayList<Integer>> adj, int u, int par) { // Store the immediate parent parent.set(u,par); // Traverse the children of // the current node for(int child : adj.get(u)) { // Recursively call for // function dfs for the // child node if (child != par) dfs(parent, adj, child, u); } } // Function to count the number of // ancestors with values smaller // than that of the current node static void countSmallerAncestors( ArrayList<ArrayList<Integer>> adj, int n) { // Stores the parent of each node ArrayList<Integer> parent = new ArrayList<Integer>(); for(int i = 0; i < (int)(1e5); i++) { parent.add(0); } // Perform the DFS Traversal dfs(parent, adj, 1, -1); // Traverse all the nodes for(int i = 1; i <= n; i++) { int node = i; // Store the number of ancestors // smaller than node int cnt = 0; // Loop until parent[node] != -1 while (parent.get(node) != -1) { // If the condition satisfies, // increment cnt by 1 if (parent.get(node) < i) cnt += 1; node = parent.get(node); } // Print the required result // for the current node System.out.print(cnt + " "); } } // Driver code public static void main (String[] args) { int N = 6; ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < (int)(1e5); i++) { adj.add(new ArrayList<Integer>()); } // Tree Formation add_edge(adj, 1, 5); add_edge(adj, 1, 4); add_edge(adj, 4, 6); add_edge(adj, 5, 3); add_edge(adj, 5, 2); countSmallerAncestors(adj, N); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach # Function to add an edge # between nodes u and v def add_edge(u, v): global adj adj[u].append(v) adj[v].append(u) # Function to perform the DFS Traversal # and store parent of each node def dfs(u, par = -1): global adj, parent # Store the immediate parent parent[u] = par # Traverse the children of # the current node for child in adj[u]: # Recursively call for # function dfs for the # child node if (child != par): dfs(child, u) # Function to count the number of # ancestors with values smaller # than that of the current node def countSmallerAncestors(n): global parent, adj # Stores the parent of each node # Perform the DFS Traversal dfs(1) # Traverse all the nodes for i in range(1, n + 1): node = i # Store the number of ancestors # smaller than node cnt = 0 # Loop until parent[node] != -1 while (parent[node] != -1): # If the condition satisfies, # increment cnt by 1 if (parent[node] < i): cnt += 1 node = parent[node] # Print the required result # for the current node print(cnt, end = " ") # Driver Code if __name__ == '__main__': N = 6 adj = [[] for i in range(10**5)] parent = [0] * (10**5) # Tree Formation add_edge(1, 5) add_edge(1, 4) add_edge(4, 6) add_edge(5, 3) add_edge(5, 2) countSmallerAncestors(N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to add an edge // between nodes u and v static void add_edge(List<List<int>> adj, int u, int v) { adj[u].Add(v); adj[v].Add(u); } // Function to perform the DFS Traversal // and store parent of each node static void dfs(List<int> parent, List<List<int>> adj, int u, int par = -1) { // Store the immediate parent parent[u] = par; // Traverse the children of // the current node foreach(int child in adj[u]) { // Recursively call for // function dfs for the // child node if (child != par) dfs(parent, adj, child, u); } } // Function to count the number of // ancestors with values smaller // than that of the current node static void countSmallerAncestors( List<List<int>> adj, int n) { // Stores the parent of each node List<int> parent = new List<int>(); for(int i = 0; i < (int)(1e5); i++) { parent.Add(0); } // Perform the DFS Traversal dfs(parent, adj, 1); // Traverse all the nodes for (int i = 1; i <= n; i++) { int node = i; // Store the number of ancestors // smaller than node int cnt = 0; // Loop until parent[node] != -1 while (parent[node] != -1) { // If the condition satisfies, // increment cnt by 1 if (parent[node] < i) cnt += 1; node = parent[node]; } // Print the required result // for the current node Console.Write(cnt + " "); } } static void Main() { int N = 6; List<List<int>> adj = new List<List<int>>(); for(int i = 0; i < (int)(1e5); i++) { adj.Add(new List<int>()); } // Tree Formation add_edge(adj, 1, 5); add_edge(adj, 1, 4); add_edge(adj, 4, 6); add_edge(adj, 5, 3); add_edge(adj, 5, 2); countSmallerAncestors(adj, N); } }
Javascript
<script> // JavaScript program for the above approach // Function to add an edge // between nodes u and v function add_edge(adj, u, v) { adj[u].push(v); adj[v].push(u); } // Function to perform the DFS Traversal // and store parent of each node function dfs(parent, adj, u, par = -1) { // Store the immediate parent parent[u] = par; // Traverse the children of // the current node adj[u].forEach(child => { // Recursively call for // function dfs for the // child node if (child != par) dfs(parent, adj, child, u); }); } // Function to count the number of // ancestors with values smaller // than that of the current node function countSmallerAncestors(adj, n) { // Stores the parent of each node var parent = Array(100000).fill(0); // Perform the DFS Traversal dfs(parent, adj, 1); // Traverse all the nodes for (var i = 1; i <= n; i++) { var node = i; // Store the number of ancestors // smaller than node var cnt = 0; // Loop until parent[node] != -1 while (parent[node] != -1) { // If the condition satisfies, // increment cnt by 1 if (parent[node] < i) cnt += 1; node = parent[node]; } // Print the required result // for the current node document.write( cnt + " "); } } // Driver Code var N = 6; var adj = Array.from(Array(100000), ()=>Array()); // Tree Formation add_edge(adj, 1, 5); add_edge(adj, 1, 4); add_edge(adj, 4, 6); add_edge(adj, 5, 3); add_edge(adj, 5, 2); countSmallerAncestors(adj, N); </script>
0 1 1 1 1 2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kfardeen7890 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA