Ancho promedio en un árbol N-ario

Dado un árbol genérico que consta de N Nodes, la tarea es encontrar el ancho promedio para cada Node presente en el árbol dado.

El ancho promedio de cada Node se puede calcular mediante la relación entre el número total de Nodes en ese subárbol (incluido el Node en sí) y el número total de niveles debajo de ese Node.

Ejemplos:

Entrada:
              1
           / \
        2 3
     / \ / \ \
  4 5 6 7 8
Salida: 1:2, 2:1, 3:2, 4:1, 5:1, 6:1, 7:1, 8:1
Explicación: El ancho promedio de cada Node se puede calcular como
Para el Node 1: 8/3 = 2
Para el Node 2: 3/2 = 1
Para el Node 3: 4/2 = 2
Para el Node 4: 1/1 = 1
Para el Node 5: 1/1 = 1
Para Node 6: 1/1 = 1
Para Node 7: 1/1 = 1
Para Node 8: 1/1 = 1

Enfoque: el ancho promedio se puede calcular encontrando el tamaño del subárbol de cada Node en el árbol N-ario y el nivel o la altura de cada Node en el árbol N-ario . Ambos se pueden calcular utilizando un solo recorrido DFS .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > ans;
 
// Node structure
struct Node {
    int val;
    vector<Node*> child;
};
 
// Utility function to create a new
// tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->val = key;
    return temp;
}
 
// Function to find levels and
// subtree sizes
vector<int> UtilityFun(Node* root, vector<vector<int> >& ans)
{
    if (root == nullptr)
        return { 0, 0 };
 
    // Num nodes and level with just
    // a single node
    int totalNodes = 1, totalLevels = 1;
 
    // Recur for all children
    for (int i = 0; i < root->child.size(); i++) {
        vector<int> info = UtilityFun(root->child[i], ans);
        totalNodes += info[0];
        totalLevels = max(totalLevels, 1 + info[1]);
    }
 
    // Finding the current Width
    int currentAverageWidth = totalNodes / totalLevels;
 
    // Storing in ans
    ans.push_back({ root->val, currentAverageWidth });
 
    return { totalNodes, totalLevels };
}
 
// Function to find the average width
// of all nodes
vector<vector<int> > findAvgWidth(Node* root)
{
    if (root == nullptr)
        return {};
 
    // Function Call
    UtilityFun(root, ans);
    return ans;
}
 
// Function to display the values
void display(vector<vector<int> > ans)
{
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i][0] << ":" << ans[i][1] << ", ";
    }
}
 
// Driver Code
int main()
{
    // Given Input
    Node* root = newNode(1);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child[0]->child).push_back(newNode(4));
    (root->child[1]->child).push_back(newNode(5));
    (root->child[0]->child).push_back(newNode(6));
    (root->child[1])->child.push_back(newNode(7));
    (root->child[1]->child).push_back(newNode(8));
 
    // Function Call
    findAvgWidth(root);
 
    // Function Call
    display(ans);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
    static Vector<Vector<Integer>> ans = new Vector<Vector<Integer>>();
     
    // Node structure
    static class Node {
         
        public int val;
        public Vector<Node> child;
         
        public Node(int key)
        {
            val = key;
            child = new Vector<Node>();
        }
    }
     
    // Utility function to create a new
    // tree node
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
   
    // Function to find levels and
    // subtree sizes
    static Vector<Integer> UtilityFun(Node root, Vector<Vector<Integer>> ans)
    {
        if (root == null)
        {
            Vector<Integer> temp = new Vector<Integer>();
            temp.add(0);
            temp.add(0);
            return temp;
        }
   
        // Num nodes and level with just
        // a single node
        int totalNodes = 1, totalLevels = 1;
   
        // Recur for all children
        for (int i = 0; i < root.child.size(); i++) {
            Vector<Integer> info = UtilityFun(root.child.get(i), ans);
            totalNodes += info.get(0);
            totalLevels = Math.max(totalLevels, 1 + info.get(1));
        }
   
        // Finding the current Width
        int currentAverageWidth = totalNodes / totalLevels;
   
        // Storing in ans
        Vector<Integer> temp = new Vector<Integer>();
        temp.add(root.val);
        temp.add(currentAverageWidth);
        ans.add(temp);
         
        temp = new Vector<Integer>();
        temp.add(totalNodes);
        temp.add(totalLevels);
   
        return temp;
    }
   
    // Function to find the average width
    // of all nodes
    static Vector<Vector<Integer>> findAvgWidth(Node root)
    {
        if (root == null)
            return new Vector<Vector<Integer>>();
   
        // Function Call
        UtilityFun(root, ans);
        return ans;
    }
   
    // Function to display the values
    static void display(Vector<Vector<Integer>> ans)
    {
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i).get(0) + ":" + ans.get(i).get(1) + ", ");
        }
    }
     
    public static void main(String[] args)
    {
        // Given Input
        Node root = newNode(1);
        (root.child).add(newNode(2));
        (root.child).add(newNode(3));
        (root.child.get(0).child).add(newNode(4));
        (root.child.get(1).child).add(newNode(5));
        (root.child.get(0).child).add(newNode(6));
        (root.child.get(1)).child.add(newNode(7));
        (root.child.get(1).child).add(newNode(8));
         
        // Function Call
        findAvgWidth(root);
         
        // Function Call
        display(ans);
    }
}
 
// This code is contributed by suresh07.

# Python3 program for the above approach
ans = []
 
# Node structure
class Node:
    def __init__(self, key):
        self.val = key
        self.child = []
 
# Utility function to create a new
# tree node
def newNode(key):
    temp = Node(key)
    return temp
 
# Function to find levels and
# subtree sizes
def UtilityFun(root, ans):
    if (root == None):
        return [ 0, 0 ]
 
    # Num nodes and level with just
    # a single node
    totalNodes, totalLevels = 1, 1
 
    # Recur for all children
    for i in range(len(root.child)):
        info = UtilityFun(root.child[i], ans)
        totalNodes += info[0]
        totalLevels = max(totalLevels, 1 + info[1])
 
    # Finding the current Width
    currentAverageWidth = int(totalNodes / totalLevels)
 
    # Storing in ans
    ans.append([ root.val, currentAverageWidth ])
 
    return [ totalNodes, totalLevels ]
 
# Function to find the average width
# of all nodes
def findAvgWidth(root):
    if (root == None):
        return []
 
    # Function Call
    UtilityFun(root, ans)
    return ans
 
# Function to display the values
def display(ans):
    for i in range(len(ans)):
        print(ans[i][0], ":", ans[i][1], ", ", sep="",end="")
 
# Given Input
root = newNode(1)
(root.child).append(newNode(2))
(root.child).append(newNode(3))
(root.child[0].child).append(newNode(4))
(root.child[1].child).append(newNode(5))
(root.child[0].child).append(newNode(6))
(root.child[1]).child.append(newNode(7))
(root.child[1].child).append(newNode(8))
 
# Function Call
findAvgWidth(root)
 
# Function Call
display(ans)
 
# This code is contributed by divyesh072019.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    static List<List<int>> ans = new List<List<int>>();
     
    // Node structure
    class Node {
        
        public int val;
        public List<Node> child;
        
        public Node(int key)
        {
            val = key;
            child = new List<Node>();
        }
    }
     
    // Utility function to create a new
    // tree node
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
  
    // Function to find levels and
    // subtree sizes
    static List<int> UtilityFun(Node root, List<List<int>> ans)
    {
        if (root == null)
        {
            List<int> temp = new List<int>();
            temp.Add(0);
            temp.Add(0);
            return temp;
        }
  
        // Num nodes and level with just
        // a single node
        int totalNodes = 1, totalLevels = 1;
  
        // Recur for all children
        for (int i = 0; i < root.child.Count; i++) {
            List<int> info = UtilityFun(root.child[i], ans);
            totalNodes += info[0];
            totalLevels = Math.Max(totalLevels, 1 + info[1]);
        }
  
        // Finding the current Width
        int currentAverageWidth = totalNodes / totalLevels;
  
        // Storing in ans
        ans.Add(new List<int>{root.val, currentAverageWidth});
  
        return new List<int>{totalNodes, totalLevels};
    }
  
    // Function to find the average width
    // of all nodes
    static List<List<int>> findAvgWidth(Node root)
    {
        if (root == null)
            return new List<List<int>>();
  
        // Function Call
        UtilityFun(root, ans);
        return ans;
    }
  
    // Function to display the values
    static void display(List<List<int>> ans)
    {
        for (int i = 0; i < ans.Count; i++) {
            Console.Write(ans[i][0] + ":" + ans[i][1] + ", ");
        }
    }
     
  static void Main()
  {
     
    // Given Input
    Node root = newNode(1);
    (root.child).Add(newNode(2));
    (root.child).Add(newNode(3));
    (root.child[0].child).Add(newNode(4));
    (root.child[1].child).Add(newNode(5));
    (root.child[0].child).Add(newNode(6));
    (root.child[1]).child.Add(newNode(7));
    (root.child[1].child).Add(newNode(8));
    
    // Function Call
    findAvgWidth(root);
    
    // Function Call
    display(ans);
  }
}
 
// This code is contributed by mukesh07.

<script>
    // Javascript program for the above approach 
     
    let ans = []
     
    // Node structure
    class Node
    {
        constructor(key) {
           this.child = [];
           this.val = key;
        }
    }
     
    // Utility function to create a new
    // tree node
    function newNode(key)
    {
        let temp = new Node(key);
        return temp;
    }
 
    // Function to find levels and
    // subtree sizes
    function UtilityFun(root, ans)
    {
        if (root == null)
            return [ 0, 0 ];
 
        // Num nodes and level with just
        // a single node
        let totalNodes = 1, totalLevels = 1;
 
        // Recur for all children
        for (let i = 0; i < root.child.length; i++) {
            let info = UtilityFun(root.child[i], ans);
            totalNodes += info[0];
            totalLevels = Math.max(totalLevels, 1 + info[1]);
        }
 
        // Finding the current Width
        let currentAverageWidth = parseInt(totalNodes / totalLevels, 10);
 
        // Storing in ans
        ans.push([ root.val, currentAverageWidth ]);
 
        return [ totalNodes, totalLevels ];
    }
 
    // Function to find the average width
    // of all nodes
    function findAvgWidth(root)
    {
        if (root == null)
            return [];
 
        // Function Call
        UtilityFun(root, ans);
        return ans;
    }
 
    // Function to display the values
    function display(ans)
    {
        for (let i = 0; i < ans.length; i++) {
            document.write(ans[i][0] + ":" + ans[i][1] + ", ");
        }
    }
     
    // Given Input
    let root = newNode(1);
    (root.child).push(newNode(2));
    (root.child).push(newNode(3));
    (root.child[0].child).push(newNode(4));
    (root.child[1].child).push(newNode(5));
    (root.child[0].child).push(newNode(6));
    (root.child[1]).child.push(newNode(7));
    (root.child[1].child).push(newNode(8));
   
    // Function Call
    findAvgWidth(root);
   
    // Function Call
    display(ans);
 
// This code is contributed by rameshtravel07.
</script>

4:1, 6:1, 2:1, 5:1, 7:1, 8:1, 3:2, 1:2, 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)