Compter les ancêtres avec une valeur plus petite pour chaque nœud d’un arbre binaire

using System;

using System.Collections.Generic;

class GFG {

    

    

    

    static void add_edge(List<List<int>> adj, int u, int v)

    {

        adj[u].Add(v);

        adj[v].Add(u);

    }

     

    

    

    static void dfs(List<int> parent,

             List<List<int>> adj,

             int u,

             int par = -1)

    {

        

        parent[u] = par;

     

        

        

        foreach(int child in adj[u]) {

     

            

            

            

            if (child != par)

                dfs(parent, adj, child, u);

        }

    }

     

    

    

    

    static void countSmallerAncestors(

        List<List<int>> adj, int n)

    {

        

        List<int> parent = new List<int>();

        for(int i = 0; i < (int)(1e5); i++)

        {

            parent.Add(0);

        }

     

        

        dfs(parent, adj, 1);

     

        

        for (int i = 1; i <= n; i++) {

     

            int node = i;

     

            

            

            int cnt = 0;

     

            

            while (parent[node] != -1) {

     

                

                

                if (parent[node] < i)

                    cnt += 1;

     

                node = parent[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>());

    }

 

    

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

  }

}

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut