Producto de todos los Nodes hoja del árbol binario.

Dado un árbol binario, encuentre el producto de todos los Nodes hoja.
Ejemplos: 
 

Input : 
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
          \
           8
Output :
product = 4 * 5 * 8 * 7 = 1120

La idea es atravesar el árbol de cualquier manera y verificar si el Node es el Node hoja o no. Si el Node es el Node hoja, multiplique los datos del Node por una variable prod utilizada para almacenar los productos de los Nodes hoja.
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// CPP program to find product of
// all leaf nodes of binary tree
#include <bits/stdc++.h>
using namespace std;
 
// struct binary tree node
struct Node {
    int data;
    Node *left, *right;
};
 
// return new node
Node* newNode(int data)
{
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// utility function which calculates
// product of all leaf nodes
void leafProduct(Node* root, int& prod)
{
    if (!root)
        return;
 
    // product root data to prod if
    // root is a leaf node
    if (!root->left && !root->right)
        prod *= root->data;
 
    // propagate recursively in left
    // and right subtree
    leafProduct(root->left, prod);
    leafProduct(root->right, prod);
}
 
// Driver program
int main()
{
 
    // construct binary tree
    Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right = newNode(3);
    root->right->right = newNode(7);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);
 
    // variable to store product of leaf nodes
    int prod = 1;
    leafProduct(root, prod);
    cout << prod << endl;
    return 0;
}

Java

// Java program to find product of
// all leaf nodes of binary tree
class GFG
{
     
// struct binary tree node
static class Node
{
    int data;
    Node left, right;
};
 
// return new node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
 
// product
static int prod = 1;
 
// utility function which calculates
// product of all leaf nodes
static void leafProduct(Node root )
{
    if (root == null)
        return;
 
    // product root data to prod if
    // root is a leaf node
    if (root.left == null && root.right == null)
        prod *= root.data;
 
    // propagate recursively in left
    // and right subtree
    leafProduct(root.left);
    leafProduct(root.right);
}
 
// Driver program
public static void main(String args[])
{
 
    // construct binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right = newNode(3);
    root.right.right = newNode(7);
    root.right.left = newNode(6);
    root.right.left.right = newNode(8);
 
    // variable to store product of leaf nodes
    prod = 1;
    leafProduct(root);
    System.out.println(prod );
}
}
 
// This code is contributed by Arnab Kundu

Python

# Python program to find product of
# all leaf nodes of binary tree
 
# Node class
class Node:
     
    # Function to initialise the node object
    def __init__(self, data):
        self.data = data # Assign data
        self.next =None
 
# return new node
def newNode( data) :
 
    temp = Node(0)
    temp.data = data
    temp.left = temp.right = None
    return temp
 
# product
prod = 1
 
# utility function which calculates
# product of all leaf nodes
def leafProduct( root ) :
 
    global prod
    if (root == None) :
        return
 
    # product root data to prod if
    # root is a leaf node
    if (root.left == None and root.right == None):
        prod *= root.data
 
    # propagate recursively in left
    # and right subtree
    leafProduct(root.left)
    leafProduct(root.right)
 
# Driver program
 
# construct binary tree
root = newNode(1)
root.left = newNode(2)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right = newNode(3)
root.right.right = newNode(7)
root.right.left = newNode(6)
root.right.left.right = newNode(8)
 
# variable to store product of leaf nodes
prod = 1
leafProduct(root)
print(prod )
 
# This code is contributed by Arnab Kundu

C#

// C# program to find product of
// all leaf nodes of binary tree
using System;
 
class GFG
{
     
// struct binary tree node
public class Node
{
    public int data;
    public Node left, right;
};
 
// return new node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
}
 
// product
static int prod = 1;
 
// utility function which calculates
// product of all leaf nodes
static void leafProduct(Node root )
{
    if (root == null)
        return;
 
    // product root data to prod if
    // root is a leaf node
    if (root.left == null && root.right == null)
        prod *= root.data;
 
    // propagate recursively in left
    // and right subtree
    leafProduct(root.left);
    leafProduct(root.right);
}
 
// Driver code
public static void Main(String []args)
{
 
    // construct binary tree
    Node root = newNode(1);
    root.left = newNode(2);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right = newNode(3);
    root.right.right = newNode(7);
    root.right.left = newNode(6);
    root.right.left.right = newNode(8);
 
    // variable to store product of leaf nodes
    prod = 1;
    leafProduct(root);
    Console.WriteLine(prod );
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// javascript program to find product of
// all leaf nodes of binary tree
// struct binary tree node
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}
 
    // return new node
    function newNode(data) {
var temp = new Node();
        temp.data = data;
        temp.left = temp.right = null;
        return temp;
    }
 
    // product
    var prod = 1;
 
    // utility function which calculates
    // product of all leaf nodes
    function leafProduct(root) {
        if (root == null)
            return;
 
        // product root data to prod if
        // root is a leaf node
        if (root.left == null && root.right == null)
            prod *= root.data;
 
        // propagate recursively in left
        // and right subtree
        leafProduct(root.left);
        leafProduct(root.right);
    }
 
    // Driver program
     
 
        // construct binary tree
var root = newNode(1);
        root.left = newNode(2);
        root.left.left = newNode(4);
        root.left.right = newNode(5);
        root.right = newNode(3);
        root.right.right = newNode(7);
        root.right.left = newNode(6);
        root.right.left.right = newNode(8);
 
        // variable to store product of leaf nodes
        prod = 1;
        leafProduct(root);
        document.write(prod);
 
// This code contributed by gauravrajput1
</script>
Producción: 

1120

 

Complejidad de tiempo: O(n), donde n es el número total de Nodes en el árbol.
 

Publicación traducida automáticamente

Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *