Dado un árbol binario, devuelve el siguiente valor para él.
- Para cada nivel, calcule la suma de todas las hojas si hay hojas en este nivel. De lo contrario, ignóralo.
- Devuelve la multiplicación de todas las sumas.
Ejemplos :
Input: Root of below tree
2
/ \
7 5
\
9
Output: 63
First levels doesn't have leaves. Second level
has one leaf 7 and third level also has one
leaf 9. Therefore result is 7*9 = 63
Input: Root of below tree
2
/ \
7 5
/ \ \
8 6 9
/ \ / \
1 11 4 10
Output: 208
First two levels don't have leaves. Third
level has single leaf 8. Last level has four
leaves 1, 11, 4 and 10. Therefore result is
8 * (1 + 11 + 4 + 10)
En el artículo anterior , hemos visto una solución basada en colas que utiliza el orden transversal de niveles .
Aquí, simplemente estamos haciendo un recorrido de preorden del árbol binario , y hemos usado unordered_map en C++ STL para almacenar la suma de los Nodes hoja en el mismo nivel. Luego, en un solo recorrido del mapa, hemos calculado el producto final de las sumas de nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find product of sums
// of data of leaves at same levels
// using map in STL
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node {
int data;
Node* left;
Node* right;
};
// Utility function to create
// a new Tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Helper function to calculate sum of
// leaf nodes at same level and store in
// an unordered_map
void productOfLevelSumUtil(Node* root,
unordered_map<int, int>& level_sum,
int level)
{
if (!root)
return;
// Check if current node is a leaf node
// If yes add it to sum of current level
if (!root->left && !root->right)
level_sum[level] += root->data;
// Traverse left subtree
productOfLevelSumUtil(root->left, level_sum,
level + 1);
// Traverse right subtree
productOfLevelSumUtil(root->right, level_sum,
level + 1);
}
// Function to calculate product of level sums
int productOfLevelSum(Node* root)
{
// Create a map to store sum of leaf
// nodes at same levels.
unordered_map<int, int> level_sum;
// Call the helper function to
// calculate level sums of leaf nodes
productOfLevelSumUtil(root, level_sum, 0);
// variable to store final product
int prod = 1;
// Traverse the map to calculate product
// of level sums
for (auto it = level_sum.begin();
it != level_sum.end(); it++)
prod *= it->second;
// Return the result
return prod;
}
// Driver Code
int main()
{
// Creating Binary Tree
Node* root = newNode(2);
root->left = newNode(7);
root->right = newNode(5);
root->left->right = newNode(6);
root->left->left = newNode(8);
root->left->right->left = newNode(1);
root->left->right->right = newNode(11);
root->right->right = newNode(9);
root->right->right->left = newNode(4);
root->right->right->right = newNode(10);
cout << "Final product is = "
<< productOfLevelSum(root) << endl;
return 0;
}
Java
// Java program to find product of sums
// of data of leaves at same levels
// using map in STL
import java.util.*;
public class GFG
{
// Binary Tree Node
static class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
// Root of the Binary Tree
Node root;
public GFG()
{
root = null;
}
// Utility function to create
// a new Tree node
static Node newNode(int data)
{
Node temp = new Node(data);
return (temp);
}
// Create a map to store sum of leaf
// nodes at same levels.
static HashMap<Integer, Integer> level_sum = new HashMap<>();
// Helper function to calculate sum of
// leaf nodes at same level and store in
// an unordered_map
static void productOfLevelSumUtil(Node root, int level)
{
if (root == null)
return;
// Check if current node is a leaf node
// If yes add it to sum of current level
if (root.left == null && root.right == null)
{
if(level_sum.containsKey(level))
{
level_sum.put(level, level_sum.get(level) + root.data);
}
else{
level_sum.put(level, root.data);
}
}
// Traverse left subtree
productOfLevelSumUtil(root.left, level + 1);
// Traverse right subtree
productOfLevelSumUtil(root.right, level + 1);
}
// Function to calculate product of level sums
static int productOfLevelSum(Node root)
{
// Call the helper function to
// calculate level sums of leaf nodes
productOfLevelSumUtil(root, 0);
// variable to store final product
int prod = 1;
// Traverse the map to calculate product
// of level sums
for (Map.Entry<Integer, Integer> it : level_sum.entrySet())
{
prod *= it.getValue();
}
// Return the result
return prod;
}
public static void main(String[] args) {
// Creating Binary Tree
GFG tree = new GFG();
tree.root = newNode(2);
tree.root.left = newNode(7);
tree.root.right = newNode(5);
tree.root.left.right = newNode(6);
tree.root.left.left = newNode(8);
tree.root.left.right.left = newNode(1);
tree.root.left.right.right = newNode(11);
tree.root.right.right = newNode(9);
tree.root.right.right.left = newNode(4);
tree.root.right.right.right = newNode(10);
System.out.print("Final product is = " + productOfLevelSum(tree.root));
}
}
// This code is contributed by divyeshrabadiya07.
C#
// C# program to find product of sums
// of data of leaves at same levels
// using map in STL
using System;
using System.Collections;
using System.Collections.Generic;
// Binary Tree Node
class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class GFG {
// Root of the Binary Tree
Node root;
public GFG()
{
root = null;
}
// Utility function to create
// a new Tree node
static Node newNode(int data)
{
Node temp = new Node(data);
return (temp);
}
// Create a map to store sum of leaf
// nodes at same levels.
static Dictionary<int, int> level_sum = new Dictionary<int, int>();
// Helper function to calculate sum of
// leaf nodes at same level and store in
// an unordered_map
static void productOfLevelSumUtil(Node root, int level)
{
if (root == null)
return;
// Check if current node is a leaf node
// If yes add it to sum of current level
if (root.left == null && root.right == null)
{
if(level_sum.ContainsKey(level))
{
level_sum[level] += root.data;
}
else{
level_sum[level] = root.data;
}
}
// Traverse left subtree
productOfLevelSumUtil(root.left, level + 1);
// Traverse right subtree
productOfLevelSumUtil(root.right, level + 1);
}
// Function to calculate product of level sums
static int productOfLevelSum(Node root)
{
// Call the helper function to
// calculate level sums of leaf nodes
productOfLevelSumUtil(root, 0);
// variable to store final product
int prod = 1;
// Traverse the map to calculate product
// of level sums
foreach(KeyValuePair<int, int> it in level_sum)
{
prod *= it.Value;
}
// Return the result
return prod;
}
static void Main() {
// Creating Binary Tree
GFG tree = new GFG();
tree.root = newNode(2);
tree.root.left = newNode(7);
tree.root.right = newNode(5);
tree.root.left.right = newNode(6);
tree.root.left.left = newNode(8);
tree.root.left.right.left = newNode(1);
tree.root.left.right.right = newNode(11);
tree.root.right.right = newNode(9);
tree.root.right.right.left = newNode(4);
tree.root.right.right.right = newNode(10);
Console.Write("Final product is = " + productOfLevelSum(tree.root));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript program to find product of sums
// of data of leaves at same levels
// using map in STL
// Binary Tree Node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Utility function to create
// a new Tree node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Create a map to store sum of leaf
// nodes at same levels.
let level_sum = new Map();
// Helper function to calculate sum of
// leaf nodes at same level and store in
// an unordered_map
function productOfLevelSumUtil(root, level)
{
if (root == null)
return;
// Check if current node is a leaf node
// If yes add it to sum of current level
if (root.left == null && root.right == null)
{
if(level_sum.has(level))
{
level_sum.set(level, level_sum.get(level) +
root.data);
}
else{
level_sum.set(level, root.data);
}
}
// Traverse left subtree
productOfLevelSumUtil(root.left, level + 1);
// Traverse right subtree
productOfLevelSumUtil(root.right, level + 1);
}
// Function to calculate product of level sums
function productOfLevelSum(root)
{
// Call the helper function to
// calculate level sums of leaf nodes
productOfLevelSumUtil(root, 0);
// variable to store final product
let prod = 1;
// Traverse the map to calculate product
// of level sums
level_sum.forEach((value,it)=>{
prod *= value;
})
// Return the result
return prod;
}
// Creating Binary Tree
let root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.left = newNode(8);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
root.right.right.right = newNode(10);
document.write("Final product is = " + productOfLevelSum(root));
</script>
Producción:
Final product is = 208
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(N)
Donde N es el número de Nodes en el Árbol Binario.