Dado un árbol binario que consta de N Nodes, la tarea es reemplazar cada Node del árbol con el producto de todos los Nodes restantes.
Ejemplos:
Entrada:
1
/ \
2 3
/ \
4 5
Salida:
120
/ \
60 40
/ \
30 24Entrada:
2
/ \
2 3
Salida:
6
/ \
6 4
Enfoque: el problema dado se puede resolver calculando primero el producto de todos los Nodes en el árbol dado y luego realizando cualquier recorrido de árbol en el árbol dado y actualizando cada Node por el valor (P/(raíz->valores) . Siga el pasos a continuación para resolver el problema:
- Encuentre el producto de todos los Nodes del árbol binario usando Preorder Traversal y guárdelo en una variable, digamos P .
- Defina una función , diga updateTree(root, P) y realice los siguientes pasos:
- Si el valor de root es NULL , entonces regrese de la función.
- Actualice el valor actual del Node raíz al valor (P/root->value) .
- Llame recursivamente al subárbol izquierdo y derecho como updateTree(root->left, P) y updateTree(root->right, P) .
- Después de completar los pasos anteriores, imprima el recorrido en orden del árbol modificado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A Tree node
class Node {
public:
int data;
Node *left, *right;
// Constructor
Node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function to create a new node in
// the given Tree
Node* newNode(int value)
{
Node* temp = new Node(value);
return (temp);
}
// Function to find the product of
// all the nodes in the given Tree
int findProduct(Node* root)
{
// Base Case
if (root == NULL)
return 1;
// Recursively Call for the left
// and the right subtree
return (root->data
* findProduct(root->left)
* findProduct(root->right));
}
// Function to perform the Inorder
// traversal of the given tree
void display(Node* root)
{
// Base Case
if (root == NULL)
return;
// Recursively call for the
// left subtree
display(root->left);
// Print the value
cout << root->data << " ";
// Recursively call for the
// right subtree
display(root->right);
}
// Function to convert the given tree
// to the multiplication tree
void convertTree(int product,
Node* root)
{
// Base Case
if (root == NULL)
return;
// Divide the total product by
// the root's data
root->data = product / (root->data);
// Go to the left subtree
convertTree(product, root->left);
// Go to the right subtree
convertTree(product, root->right);
}
// Driver Code
int main()
{
// Given Binary Tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
cout << "Inorder Traversal of "
<< "given Tree:\n";
// Print the tree traversal
display(root);
int product = findProduct(root);
cout << "\nInorder Traversal of "
<< "given Tree:\n";
// Function Call
convertTree(product, root);
// Print the tree traversal
display(root);
return 0;
}
Python3
# Python3 program for the above approach
# A Tree node
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Function to find the product of
# all the nodes in the given Tree
def findProduct(root):
# Base Case
if (root == None):
return 1
# Recursively Call for the left
# and the right subtree
return (root.data * findProduct(root.left) *
findProduct(root.right))
# Function to perform the Inorder
# traversal of the given tree
def display(root):
# Base Case
if (root == None):
return
# Recursively call for the
# left subtree
display(root.left)
# Print the value
print(root.data, end = " ")
# Recursively call for the
# right subtree
display(root.right)
# Function to convert the given tree
# to the multiplication tree
def convertTree(product, root):
# Base Case
if (root == None):
return
# Divide the total product by
# the root's data
root.data = product // (root.data)
# Go to the left subtree
convertTree(product, root.left)
# Go to the right subtree
convertTree(product, root.right)
# Driver Code
if __name__ == '__main__':
# Given Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)
print("Inorder Traversal of given Tree: ")
# Print the tree traversal
display(root)
product = findProduct(root)
print("\nInorder Traversal of given Tree:")
# Function Call
convertTree(product, root)
# Print the tree traversal
display(root)
# This code is contributed by mohit kumar 29
Java
// Java program for the above approach
public class GFG {
// TreeNode class
static class Node {
public int data;
public Node left, right;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.left = temp.right = null;
return temp;
}
// Function to find the product of
// all the nodes in the given Tree
static int findProduct(Node root)
{
// Base Case
if (root == null)
return 1;
// Recursively Call for the left
// and the right subtree
return (root.data * findProduct(root.left)
* findProduct(root.right));
}
// Function to perform the Inorder
// traversal of the given tree
static void display(Node root)
{
// Base Case
if (root == null)
return;
// Recursively call for the
// left subtree
display(root.left);
// Print the value
System.out.print(root.data + " ");
// Recursively call for the
// right subtree
display(root.right);
}
// Function to convert the given tree
// to the multiplication tree
static void convertTree(int product, Node root)
{
// Base Case
if (root == null)
return;
// Divide the total product by
// the root's data
root.data = product / (root.data);
// Go to the left subtree
convertTree(product, root.left);
// Go to the right subtree
convertTree(product, root.right);
}
// Driver code
public static void main(String[] args)
{
// Given Binary Tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(5);
System.out.println("Inorder Traversal of "
+ "given Tree:");
// Print the tree traversal
display(root);
int product = findProduct(root);
System.out.println("\nInorder Traversal of "
+ "given Tree:");
// Function Call
convertTree(product, root);
// Print the tree traversal
display(root);
}
}
// This code is contributed by abhinavjain194
C#
// C# program for the above approach
using System;
public class GFG {
// TreeNode class
class Node {
public int data;
public Node left, right;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.left = temp.right = null;
return temp;
}
// Function to find the product of
// all the nodes in the given Tree
static int findProduct(Node root)
{
// Base Case
if (root == null)
return 1;
// Recursively Call for the left
// and the right subtree
return (root.data * findProduct(root.left)
* findProduct(root.right));
}
// Function to perform the Inorder
// traversal of the given tree
static void display(Node root)
{
// Base Case
if (root == null)
return;
// Recursively call for the
// left subtree
display(root.left);
// Print the value
Console.Write(root.data + " ");
// Recursively call for the
// right subtree
display(root.right);
}
// Function to convert the given tree
// to the multiplication tree
static void convertTree(int product, Node root)
{
// Base Case
if (root == null)
return;
// Divide the total product by
// the root's data
root.data = product / (root.data);
// Go to the left subtree
convertTree(product, root.left);
// Go to the right subtree
convertTree(product, root.right);
}
// Driver code
public static void Main(String[] args)
{
// Given Binary Tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(5);
Console.WriteLine("Inorder Traversal of "
+ "given Tree:");
// Print the tree traversal
display(root);
int product = findProduct(root);
Console.WriteLine("\nInorder Traversal of "
+ "given Tree:");
// Function Call
convertTree(product, root);
// Print the tree traversal
display(root);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// TreeNode class
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
function newNode(key) {
var temp = new Node();
temp.data = key;
temp.left = temp.right = null;
return temp;
}
// Function to find the product of
// all the nodes in the given Tree
function findProduct(root) {
// Base Case
if (root == null) return 1;
// Recursively Call for the left
// and the right subtree
return root.data * findProduct(root.left) * findProduct(root.right);
}
// Function to perform the Inorder
// traversal of the given tree
function display(root) {
// Base Case
if (root == null) return;
// Recursively call for the
// left subtree
display(root.left);
// Print the value
document.write(root.data + " ");
// Recursively call for the
// right subtree
display(root.right);
}
// Function to convert the given tree
// to the multiplication tree
function convertTree(product, root) {
// Base Case
if (root == null) return;
// Divide the total product by
// the root's data
root.data = parseInt(product / root.data);
// Go to the left subtree
convertTree(product, root.left);
// Go to the right subtree
convertTree(product, root.right);
}
// Driver code
// Given Binary Tree
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(5);
document.write("Inorder Traversal of " + "given Tree: <br>");
// Print the tree traversal
display(root);
var product = findProduct(root);
document.write("<br>Inorder Traversal of " + "given Tree:<br>");
// Function Call
convertTree(product, root);
// Print the tree traversal
display(root);
// This code is contributed by rdtank.
</script>
Producción:
Inorder Traversal of given Tree: 2 1 4 3 5 Inorder Traversal of given Tree: 60 120 30 40 24
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA