Dado un entero positivo L que representa el número de niveles en un árbol binario perfecto. Dado que los Nodes hoja en este árbol binario perfecto se numeran del 1 al n, donde n es el número de Nodes hoja. Y el Node padre es la suma de los dos Nodes hijos. Nuestra tarea es escribir un programa para imprimir la suma de todos los Nodes de este árbol binario perfecto.
Ejemplos:
Input : L = 3
Output : 30
Explanation : Tree will be - 10
/ \
3 7
/ \ / \
1 2 3 4
Input : L = 2
Output : 6
Explanation : Tree will be - 3
/ \
1 2
Enfoque ingenuo : la solución más simple es generar primero el valor de todos los Nodes del árbol binario perfecto y luego calcular la suma de todos los Nodes. Primero podemos generar todos los Nodes hoja y luego proceder de abajo hacia arriba para generar el resto de los Nodes. Sabemos que en un árbol binario perfecto, el número de Nodes hoja puede estar dado por 2 L-1 , donde L es el número de niveles. El número de Nodes en un árbol binario perfecto a medida que nos movemos hacia arriba desde la parte inferior se reducirá a la mitad.
A continuación se muestra la implementación de la idea anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// function to find sum of all of the nodes
// of given perfect binary tree
int sumNodes(int l)
{
// no of leaf nodes
int leafNodeCount = pow(2, l - 1);
// list of vector to store nodes of
// all of the levels
vector<int> vec[l];
// store the nodes of last level
// i.e., the leaf nodes
for (int i = 1; i <= leafNodeCount; i++)
vec[l - 1].push_back(i);
// store nodes of rest of the level
// by moving in bottom-up manner
for (int i = l - 2; i >= 0; i--) {
int k = 0;
// loop to calculate values of parent nodes
// from the children nodes of lower level
while (k < vec[i + 1].size() - 1) {
// store the value of parent node as
// sum of children nodes
vec[i].push_back(vec[i + 1][k] +
vec[i + 1][k + 1]);
k += 2;
}
}
int sum = 0;
// traverse the list of vector
// and calculate the sum
for (int i = 0; i < l; i++) {
for (int j = 0; j < vec[i].size(); j++)
sum += vec[i][j];
}
return sum;
}
// Driver Code
int main()
{
int l = 3;
cout << sumNodes(l);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// function to find sum of
// all of the nodes of given
// perfect binary tree
static int sumNodes(int l)
{
// no of leaf nodes
int leafNodeCount = (int)Math.pow(2, l - 1);
// list of vector to store
// nodes of all of the levels
Vector<Vector
<Integer>> vec = new Vector<Vector
<Integer>>();
//initialize
for (int i = 1; i <= l; i++)
vec.add(new Vector<Integer>());
// store the nodes of last level
// i.e., the leaf nodes
for (int i = 1;
i <= leafNodeCount; i++)
vec.get(l - 1).add(i);
// store nodes of rest of
// the level by moving in
// bottom-up manner
for (int i = l - 2; i >= 0; i--)
{
int k = 0;
// loop to calculate values
// of parent nodes from the
// children nodes of lower level
while (k < vec.get(i + 1).size() - 1)
{
// store the value of parent
// node as sum of children nodes
vec.get(i).add(vec.get(i + 1).get(k) +
vec.get(i + 1).get(k + 1));
k += 2;
}
}
int sum = 0;
// traverse the list of vector
// and calculate the sum
for (int i = 0; i < l; i++)
{
for (int j = 0;
j < vec.get(i).size(); j++)
sum += vec.get(i).get(j);
}
return sum;
}
// Driver Code
public static void main(String args[])
{
int l = 3;
System.out.println(sumNodes(l));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to implement the # above approach # function to find Sum of all of the # nodes of given perfect binary tree def SumNodes(l): # no of leaf nodes leafNodeCount = pow(2, l - 1) # list of vector to store nodes of # all of the levels vec = [[] for i in range(l)] # store the nodes of last level # i.e., the leaf nodes for i in range(1, leafNodeCount + 1): vec[l - 1].append(i) # store nodes of rest of the level # by moving in bottom-up manner for i in range(l - 2, -1, -1): k = 0 # loop to calculate values of parent nodes # from the children nodes of lower level while (k < len(vec[i + 1]) - 1): # store the value of parent node as # Sum of children nodes vec[i].append(vec[i + 1][k] + vec[i + 1][k + 1]) k += 2 Sum = 0 # traverse the list of vector # and calculate the Sum for i in range(l): for j in range(len(vec[i])): Sum += vec[i][j] return Sum # Driver Code if __name__ == '__main__': l = 3 print(SumNodes(l)) # This code is contributed by PranchalK
C#
using System;
using System.Collections.Generic;
// C# program to implement
// the above approach
public class GFG
{
// function to find sum of
// all of the nodes of given
// perfect binary tree
public static int sumNodes(int l)
{
// no of leaf nodes
int leafNodeCount = (int)Math.Pow(2, l - 1);
// list of vector to store
// nodes of all of the levels
List<List<int>> vec = new List<List<int>>();
//initialize
for (int i = 1; i <= l; i++)
{
vec.Add(new List<int>());
}
// store the nodes of last level
// i.e., the leaf nodes
for (int i = 1; i <= leafNodeCount; i++)
{
vec[l - 1].Add(i);
}
// store nodes of rest of
// the level by moving in
// bottom-up manner
for (int i = l - 2; i >= 0; i--)
{
int k = 0;
// loop to calculate values
// of parent nodes from the
// children nodes of lower level
while (k < vec[i + 1].Count - 1)
{
// store the value of parent
// node as sum of children nodes
vec[i].Add(vec[i + 1][k] + vec[i + 1][k + 1]);
k += 2;
}
}
int sum = 0;
// traverse the list of vector
// and calculate the sum
for (int i = 0; i < l; i++)
{
for (int j = 0; j < vec[i].Count; j++)
{
sum += vec[i][j];
}
}
return sum;
}
// Driver Code
public static void Main(string[] args)
{
int l = 3;
Console.WriteLine(sumNodes(l));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to implement the above approach
// function to find sum of
// all of the nodes of given
// perfect binary tree
function sumNodes(l)
{
// no of leaf nodes
let leafNodeCount = Math.pow(2, l - 1);
// list of vector to store
// nodes of all of the levels
let vec = [];
//initialize
for (let i = 1; i <= l; i++)
{
vec.push([]);
}
// store the nodes of last level
// i.e., the leaf nodes
for (let i = 1; i <= leafNodeCount; i++)
{
vec[l - 1].push(i);
}
// store nodes of rest of
// the level by moving in
// bottom-up manner
for (let i = l - 2; i >= 0; i--)
{
let k = 0;
// loop to calculate values
// of parent nodes from the
// children nodes of lower level
while (k < vec[i + 1].length - 1)
{
// store the value of parent
// node as sum of children nodes
vec[i].push(vec[i + 1][k] + vec[i + 1][k + 1]);
k += 2;
}
}
let sum = 0;
// traverse the list of vector
// and calculate the sum
for (let i = 0; i < l; i++)
{
for (let j = 0; j < vec[i].length; j++)
{
sum += vec[i][j];
}
}
return sum;
}
let l = 3;
document.write(sumNodes(l));
// This code is contributed by mukesh07.
</script>
Producción:
30
Complejidad temporal : O(n), donde n es el número total de Nodes en el árbol binario perfecto.
Enfoque eficiente : un enfoque eficiente es observar que solo necesitamos encontrar la suma de todos los Nodes. Podemos obtener fácilmente la suma de todos los Nodes en el último nivel usando la fórmula de la suma de los primeros n números naturales. Además, se puede ver que, como es un árbol binario perfecto y los Nodes principales serán la suma de los Nodes secundarios, la suma de los Nodes en todos los niveles será la misma. Por lo tanto, solo necesitamos encontrar la suma de los Nodes en el último nivel y multiplicarla por el número total de niveles.
A continuación se muestra la implementación de la idea anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// function to find sum of all of the nodes
// of given perfect binary tree
int sumNodes(int l)
{
// no of leaf nodes
int leafNodeCount = pow(2, l - 1);
int sumLastLevel = 0;
// sum of nodes at last level
sumLastLevel = (leafNodeCount * (leafNodeCount + 1)) / 2;
// sum of all nodes
int sum = sumLastLevel * l;
return sum;
}
// Driver Code
int main()
{
int l = 3;
cout << sumNodes(l);
return 0;
}
Java
// Java code to find sum of all nodes
// of the given perfect binary tree
import java.io.*;
import java.lang.Math;
class GFG {
// function to find sum of
// all of the nodes of given
// perfect binary tree
static double sumNodes(int l)
{
// no of leaf nodes
double leafNodeCount = Math.pow(2, l - 1);
double sumLastLevel = 0;
// sum of nodes at last level
sumLastLevel = (leafNodeCount *
(leafNodeCount + 1)) / 2;
// sum of all nodes
double sum = sumLastLevel * l;
return sum;
}
// Driver Code
public static void main (String[] args) {
int l = 3;
System.out.println(sumNodes(l));
}
}
// This code is contributed by
// Anuj_{AJ_67}
Python3
# function to find sum of all of the nodes # of given perfect binary tree import math def sumNodes(l): # no of leaf nodes leafNodeCount = math.pow(2, l - 1); sumLastLevel = 0; # sum of nodes at last level sumLastLevel = ((leafNodeCount * (leafNodeCount + 1)) / 2); # sum of all nodes sum = sumLastLevel * l; return int(sum); # Driver Code l = 3; print (sumNodes(l)); # This code is contributed by manishshaw
C#
// C# code to find sum of all nodes
// of the given perfect binary tree
using System;
using System.Collections.Generic;
class GFG {
// function to find sum of
// all of the nodes of given
// perfect binary tree
static double sumNodes(int l)
{
// no of leaf nodes
double leafNodeCount = Math.Pow(2, l - 1);
double sumLastLevel = 0;
// sum of nodes at last level
sumLastLevel = (leafNodeCount *
(leafNodeCount + 1)) / 2;
// sum of all nodes
double sum = sumLastLevel * l;
return sum;
}
// Driver Code
public static void Main()
{
int l = 3;
Console.Write(sumNodes(l));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
// PHP code to find sum of all nodes
// of the given perfect binary tree
// function to find sum of
// all of the nodes of given
// perfect binary tree
function sumNodes($l)
{
// no of leaf nodes
$leafNodeCount = ($l - 1) *
($l - 1);
$sumLastLevel = 0;
// sum of nodes at last level
$sumLastLevel = ($leafNodeCount *
($leafNodeCount + 1)) / 2;
// sum of all nodes
$sum = $sumLastLevel * $l;
return $sum;
}
// Driver Code
$l = 3;
echo (sumNodes($l));
// This code is contributed by
// Manish Shaw (manishshaw1)
?>
Javascript
<script>
// Javascript code to find sum of all nodes
// of the given perfect binary tree
// function to find sum of
// all of the nodes of given
// perfect binary tree
function sumNodes(l)
{
// no of leaf nodes
let leafNodeCount = Math.pow(2, l - 1);
let sumLastLevel = 0;
// sum of nodes at last level
sumLastLevel = (leafNodeCount * (leafNodeCount + 1)) / 2;
// sum of all nodes
let sum = sumLastLevel * l;
return sum;
}
let l = 3;
document.write(sumNodes(l));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
30
Complejidad de tiempo : O(1)
Publicación traducida automáticamente
Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA