Dada una array arr[] de tamaño N , la tarea es generar un árbol binario completo de tal manera que la suma de los Nodes que no son hojas sea mínima, mientras que los valores del Node hoja corresponden a los elementos de la array en orden. El recorrido del árbol y el valor de cada Node que no es hoja corresponde al producto del valor de hoja más grande en el subárbol izquierdo y el subárbol derecho.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 20
Explicación:
consulte la explicación a continuación
Entrada: arr[] = {5, 2, 3}
Salida: 21
Enfoque:
para eliminar un número arr[i] , necesita un costo a * b , donde b >= a y también un elemento de la array. Para minimizar el costo de remoción, la idea es minimizar b . Para calcular el Node que no es hoja, hay dos candidatos, es decir, el primer número más grande a la izquierda y el primer número más grande a la derecha. El costo de eliminar arr[i] es un * min(left, right) . Se puede descomponer aún más para encontrar el siguiente elemento mayor en la array, a la izquierda y uno a la derecha.
Consulte: Siguiente elemento mayor
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum cost tree
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum cost tree
int MinCostTree(int arr[], int n)
{
int ans = 0;
// Stack
vector<int> st = { INT_MAX };
// Loop to traverse the array elements
for (int i = 0; i < n; i++) {
// Keep array elements
// in decreasing order by poping out
// the elements from stack till the top
// element is less than current element
while (st.back() <= arr[i]) {
// Get top element
int x = st.back();
// Remove it
st.pop_back();
// Get the minimum cost to remove x
ans += x * min(st.back(), arr[i]);
}
// Push current element
st.push_back(arr[i]);
}
// Find cost for all remaining elements
for (int i = 2; i < st.size(); i++)
ans += st[i] * st[i - 1];
return ans;
}
// Driver Code
int main()
{
int arr[] = { 5, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << MinCostTree(arr, n);
return 0;
}
Java
// Java implementation to find the
// minimum cost tree
import java.util.*;
class GFG{
// Function to find minimum cost tree
static int MinCostTree(int arr[], int n)
{
int ans = 0;
// Stack
Vector<Integer> st = new Vector<Integer>();
st.add(Integer.MAX_VALUE);
// Loop to traverse the array elements
for (int i = 0; i < n; i++) {
// Keep array elements
// in decreasing order by poping out
// the elements from stack till the top
// element is less than current element
while (st.get(st.size()-1) <= arr[i]) {
// Get top element
int x = st.get(st.size()-1);
// Remove it
st.remove(st.size()-1);
// Get the minimum cost to remove x
ans += x * Math.min(st.get(st.size()-1), arr[i]);
}
// Push current element
st.add(arr[i]);
}
// Find cost for all remaining elements
for (int i = 2; i < st.size(); i++)
ans += st.get(i) * st.get(i-1);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 2, 3 };
int n = arr.length;
// Function call
System.out.print(MinCostTree(arr, n));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation to find the # minimum cost tree # Function to find minimum cost tree def MinCostTree(arr, n): ans = 0 st = [2**32] # Loop to traverse the array elements for i in range(n): # Keep array elements # in decreasing order by poping out # the elements from stack till the top # element is less than current element while (st[-1] <= arr[i]): # Get top element x = st[-1] # Remove it st.pop() # Get the minimum cost to remove x ans += x * min(st[-1], arr[i]) # Push current element st.append(arr[i]) # Find cost for all remaining elements for i in range(2,len(st)): ans += st[i] * st[i - 1] return ans # Driver Code arr = [5, 2, 3] n = len(arr) # Function call print(MinCostTree(arr, n)) # This code is contributed by shubhamsingh10
C#
// C# implementation to find the
// minimum cost tree
using System;
using System.Collections.Generic;
class GFG
{
// Function to find minimum cost tree
static int MinCostTree(int []arr, int n)
{
int ans = 0;
// Stack
List<int> st = new List<int>();
st.Add(int.MaxValue);
// Loop to traverse the array elements
for (int i = 0; i < n; i++) {
// Keep array elements
// in decreasing order by poping out
// the elements from stack till the top
// element is less than current element
while (st[st.Count-1] <= arr[i]) {
// Get top element
int x = st[st.Count-1];
// Remove it
st.RemoveAt(st.Count-1);
// Get the minimum cost to remove x
ans += x * Math.Min(st[st.Count-1], arr[i]);
}
// Push current element
st.Add(arr[i]);
}
// Find cost for all remaining elements
for (int i = 2; i < st.Count; i++)
ans += st[i] * st[i-1];
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 2, 3 };
int n = arr.Length;
// Function call
Console.Write(MinCostTree(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the
// minimum cost tree
// Function to find minimum cost tree
function MinCostTree(arr, n)
{
let ans = 0;
// Stack
let st = new Array()
st.push(Number.MAX_SAFE_INTEGER);
// Loop to traverse the array elements
for (let i = 0; i < n; i++) {
// Keep array elements
// in decreasing order by poping out
// the elements from stack till the top
// element is less than current element
while (st[st.length -1] <= arr[i]) {
// Get top element
let x = st[st.length-1];
// Remove it
st.pop();
// Get the minimum cost to remove x
ans += x * Math.min(st[st.length - 1], arr[i]);
}
// Push current element
st.push(arr[i]);
}
// Find cost for all remaining elements
for (let i = 2; i < st.length; i++)
ans += st[i] * st[i - 1];
return ans;
}
// Driver Code
let arr = [ 5, 2, 3 ];
let n = arr.length;
// Function call
document.write(MinCostTree(arr, n));
// This code is contributed by gfgking
</script>
21
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA