Dado un árbol binario. La tarea es encontrar e imprimir el producto y la suma de todos los Nodes internos (Nodes que no son hojas) en el árbol.
En el árbol anterior, solo dos Nodes 1 y 2 son Nodes que no son hojas.
Por lo tanto, el producto de los Nodes que no son hojas = 1 * 2 = 2.
Y la suma de los Nodes que no son hojas = 1 + 2 = 3.
Ejemplos:
Input :
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Output : Product = 36, Sum = 12
Non-leaf nodes are: 1, 2, 3, 6
Enfoque: la idea es atravesar el árbol de cualquier manera y verificar si el Node actual es un Node sin hoja o no. Tome dos variables product y sum para almacenar el producto y la suma de los Nodes que no son hojas, respectivamente. Si el Node actual es un Node sin hojas, multiplique los datos del Node por el producto variable utilizado para almacenar los productos de los Nodes sin hojas y sume los datos del Node a la suma variable utilizada para almacenar la suma de los Nodes sin hojas.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to find product and sum of
// non-leaf nodes in a binary tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int data;
struct Node* left;
struct Node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Computes the product of non-leaf
// nodes in a tree
void findProductSum(struct Node* root, int& prod, int& sum)
{
// Base cases
if (root == NULL || (root->left == NULL
&& root->right == NULL))
return;
// if current node is non-leaf,
// calculate product and sum
if (root->left != NULL || root->right != NULL)
{
prod *= root->data;
sum += root->data;
}
// If root is Not NULL and its one of its
// child is also not NULL
findProductSum(root->left, prod, sum);
findProductSum(root->right, prod, sum);
}
// Driver Code
int main()
{
// Binary Tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
int prod = 1;
int sum = 0;
findProductSum(root, prod, sum);
cout <<"Product = "<<prod<<" , Sum = "<<sum;
return 0;
}
Java
// Java program to find product and sum of
// non-leaf nodes in a binary tree
class GFG
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static class Node
{
int data;
Node left;
Node right;
};
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
//int class
static class Int
{
int a;
}
// Computes the product of non-leaf
// nodes in a tree
static void findProductSum(Node root, Int prod, Int sum)
{
// Base cases
if (root == null || (root.left == null
&& root.right == null))
return;
// if current node is non-leaf,
// calculate product and sum
if (root.left != null || root.right != null)
{
prod.a *= root.data;
sum.a += root.data;
}
// If root is Not null and its one of its
// child is also not null
findProductSum(root.left, prod, sum);
findProductSum(root.right, prod, sum);
}
// Driver Code
public static void main(String args[])
{
// Binary Tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Int prod = new Int();prod.a = 1;
Int sum = new Int(); sum.a = 0;
findProductSum(root, prod, sum);
System.out.print("Product = " + prod.a + " , Sum = " + sum.a);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find product and sum
# of non-leaf nodes in a binary tree
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.
class newNode:
# Construct to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Computes the product of non-leaf
# nodes in a tree
class new:
def findProductSum(sf,root) :
# Base cases
if (root == None or (root.left == None and
root.right == None)) :
return
# if current node is non-leaf,
# calculate product and sum
if (root.left != None or
root.right != None) :
sf.prod *= root.data
sf.sum += root.data
# If root is Not None and its one
# of its child is also not None
sf.findProductSum(root.left)
sf.findProductSum(root.right)
def main(sf):
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
sf.prod = 1
sf.sum = 0
sf.findProductSum(root)
print("Product =", sf.prod,
", Sum =", sf.sum)
# Driver Code
if __name__ == '__main__':
x = new()
x.main()
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find product and sum of
// non-leaf nodes in a binary tree
using System;
class GFG
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
public class Node
{
public int data;
public Node left;
public Node right;
};
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// int class
public class Int
{
public int a;
}
// Computes the product of non-leaf
// nodes in a tree
static void findProductSum(Node root, Int prod, Int sum)
{
// Base cases
if (root == null || (root.left == null
&& root.right == null))
return;
// if current node is non-leaf,
// calculate product and sum
if (root.left != null || root.right != null)
{
prod.a *= root.data;
sum.a += root.data;
}
// If root is Not null and its one of its
// child is also not null
findProductSum(root.left, prod, sum);
findProductSum(root.right, prod, sum);
}
// Driver Code
public static void Main(String []args)
{
// Binary Tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
Int prod = new Int();prod.a = 1;
Int sum = new Int(); sum.a = 0;
findProductSum(root, prod, sum);
Console.Write("Product = " + prod.a + " , Sum = " + sum.a);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find product and sum of
// non-leaf nodes in a binary tree
/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
//var class
class Int
{
constructor(){
this.a = 0;
}
}
// Computes the product of non-leaf
// nodes in a tree
function findProductSum(root, prod, sum)
{
// Base cases
if (root == null || (root.left == null
&& root.right == null))
return;
// if current node is non-leaf,
// calculate product and sum
if (root.left != null || root.right != null)
{
prod.a *= root.data;
sum.a += root.data;
}
// If root is Not null and its one of its
// child is also not null
findProductSum(root.left, prod, sum);
findProductSum(root.right, prod, sum);
}
// Driver Code
// Binary Tree
root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
var prod = new Int();
prod.a = 1;
var sum = new Int();
sum.a = 0;
findProductSum(root, prod, sum);
document.write("Product = " + prod.a + " , Sum = " + sum.a);
// This code contributed by aashish1995
</script>
Producción:
Product = 2 , Sum = 3
Complejidad de tiempo: O(N)
Como estamos visitando cada Node solo una vez.
Espacio Auxiliar: O(h)
Aquí h es la altura del árbol y se usa espacio adicional en la pila de llamadas recursivas. En el peor de los casos (cuando el árbol está sesgado), esto puede llegar a O (N).