Cuente los antepasados ​​​​con un valor más pequeño para cada Node de un árbol binario

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *