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>
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