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>
Producción:
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