Dado un árbol binario que consta de N Nodes, la tarea es reemplazar cada Node en el árbol binario con la suma de su predecesor de orden previo y su sucesor de orden previo .
Ejemplos:
Entrada:
2
/ \
3 4
/ \ / \
6 5 7 8
Salida:
3
/ \
8 12
/ \ / \
8 10 12 7
Explicación:
- Para el Node 2: predecesor de pedido anticipado = 0 (ya que el predecesor de pedido anticipado no está presente), sucesor de pedido anticipado = 3. Suma = 3.
- Para el Node 3: predecesor de pedido anticipado = 2, sucesor de pedido anticipado = 6. Suma = 8.
- Para el Node 6: predecesor de pedido anticipado = 3, sucesor de pedido anticipado = 5. Suma = 8.
- Para el Node 5: predecesor de pedido anticipado = 6, sucesor de pedido anticipado = 4. Suma = 10.
- Para el Node 4: predecesor de pedido anticipado = 5, sucesor de pedido anticipado = 7. Suma = 12.
- Para el Node 7: predecesor de pedido anticipado = 4, sucesor de pedido anticipado = 8. Suma = 12.
- Para el Node 8: predecesor de pedido anticipado = 7, sucesor de pedido anticipado = 0 (ya que el sucesor de pedido anticipado no está presente). Suma = 7.
Entrada:
1
/ \
2 3
Salida:
2
/ \
4 2
Enfoque: el problema dado se puede resolver almacenando el recorrido del árbol en orden previo en una array auxiliar y luego reemplazando cada Node con la suma del predecesor en orden previo y el sucesor en orden previo . Siga los pasos a continuación para resolver el problema:
- Declare una función, diga replaceNode(root, A[], idx) para realizar el recorrido de preorden en el árbol con el índice de inicio como i y realice los siguientes pasos:
- Si el Node raíz es NULL , entonces regresa desde la función .
- Reemplace el valor del Node actual como V[i – 1] + V[i + 1] como para el elemento V[i] , los valores V[i – 1] y V[i + 1] son su predecesor de preorden y preorden sucesor respectivamente.
- Llame recursivamente a la función replaceNode(root->left, A[], idx + 1) y replaceNode(root->right, A[], idx + 1) .
- Inicialice un vector V que almacene el recorrido previo al pedido del árbol dado .
- Almacene 0 en el índice 0 ya que el predecesor del pedido anticipado del Node hoja más a la izquierda no existe.
- Realice el recorrido de preorden en el árbol dado y almacene el recorrido de preorden en el vector V .
- Almacene 0 al final del vector ya que el sucesor de preorden del Node de hoja más a la derecha no está presente.
- Llame a la función replaceNode(root, A[], 1) para reemplazar cada Node con la suma requerida.
- Después de completar los pasos anteriores, imprima el pedido anticipado 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; // Node of a binary tree struct Node { int data; struct Node *left, *right; }; // Function to generate a new node struct Node* getnew(int data) { // Allocate node struct Node* newnode = (struct Node*)malloc( sizeof(struct Node)); // Assign the data value newnode->data = data; newnode->left = newnode->right = NULL; return newnode; } // Function to store Preorder Traversal // of the binary tree in the vector V void StorePreorderTraversal( struct Node* root, vector<int>& v) { // If root is NULL, then return if (root == NULL) return; // Store the root's data in V v.push_back(root->data); // Recur on the left subtree StorePreorderTraversal( root->left, v); // Recur on right subtree StorePreorderTraversal( root->right, v); } // Function to replace each node of a // Binary Tree with the sum of its // preorder predecessor and successor void ReplaceNodeWithSum(struct Node* root, vector<int>& v, int& i) { // If root does not exist if (root == NULL) return; // Update the data present in the // root by the sum of its preorder // predecessor and successor root->data = v[i - 1] + v[i + 1]; // Increment index 'i' i++; // Recur on the left subtree ReplaceNodeWithSum(root->left, v, i); // Recur on the right subtree ReplaceNodeWithSum(root->right, v, i); } // Utility function to replace each // node of a binary tree with the // sum of its preorder predecessor // and successor void ReplaceNodeWithSumUtil( struct Node* root) { // If tree is empty, then return if (root == NULL) return; vector<int> v; // Stores the value of preorder // predecessor for root node v.push_back(0); // Store the preorder // traversal of the tree in V StorePreorderTraversal(root, v); // Store the value of preorder // successor for rightmost leaf v.push_back(0); // Replace each node // with the required sum int i = 1; // Function call to update // the values of the node ReplaceNodeWithSum(root, v, i); } // Function to print the preorder // traversal of a binary tree void PreorderTraversal( struct Node* root) { // If root is NULL if (root == NULL) return; // Print the data of node cout << root->data << " "; // Recur on the left subtree PreorderTraversal(root->left); // Recur on the right subtree PreorderTraversal(root->right); } // Driver Code int main() { // Binary Tree struct Node* root = getnew(2); root->left = getnew(3); root->right = getnew(4); root->left->left = getnew(6); root->left->right = getnew(5); root->right->left = getnew(7); root->right->right = getnew(8); // Print the preorder traversal // of the original tree cout << "Preorder Traversal before" << " modification of tree: "; PreorderTraversal(root); ReplaceNodeWithSumUtil(root); // Print the preorder traversal // of the modified tree cout << "\nPreorder Traversal after " << "modification of tree: "; PreorderTraversal(root); return 0; }
Java
// Java program for the above approach import java.util.Vector; class GFG{ // Node of a binary tree static class Node { int data; Node left, right; } // INT class static class INT { int data; } // Function to get a new node // of a binary tree static Node getNode(int data) { // Allocate node Node new_node = new Node(); // Put in the data; new_node.data = data; new_node.left = new_node.right = null; return new_node; } // Function to print the preorder traversal // of a binary tree static void preorderTraversal(Node root) { // If root is null if (root == null) return; // First print the data of node System.out.print(root.data + " "); // Then recur on left subtree preorderTraversal(root.left); // Now recur on right subtree preorderTraversal(root.right); } // Function to replace each node with the sum of its // preorder predecessor and successor static void replaceNodeWithSum(Node root, Vector<Integer> V, INT i) { // If root is null if (root == null) return; // Replace node's data with the sum of its // preorder predecessor and successor root.data = V.get(i.data - 1) + V.get(i.data + 1); // Move 'i' to point to the next 'V' element i.data++; // First recur on left child replaceNodeWithSum(root.left, V, i); // Now recur on right child replaceNodeWithSum(root.right, V, i); } // Function to store the preorder traversal // of the binary tree in V static void storePreorderTraversal(Node root, Vector<Integer> V) { // If root is null if (root == null) return; // Then store the root's data in 'V' V.add(root.data); // First recur on left child storePreorderTraversal(root.left, V); // Now recur on right child storePreorderTraversal(root.right, V); } // Utility function to replace each node in binary // tree with the sum of its preorder predecessor // and successor static void replaceNodeWithSumUtil(Node root) { // If tree is empty if (root == null) return; Vector<Integer> V = new Vector<Integer>(); // Store the value of preorder predecessor // for the leftmost leaf V.add(0); // Store the preorder traversal of the tree in V storePreorderTraversal(root, V); // Store the value of preorder successor // for the rightmost leaf V.add(0); // Replace each node with the required sum INT i = new INT(); i.data = 1; replaceNodeWithSum(root, V, i); } // Driver code public static void main(String[] args) { // Binary tree formation Node root = getNode(2); root.left = getNode(3); root.right = getNode(4); root.left.left = getNode(6); root.left.right = getNode(5); root.right.left = getNode(7); root.right.right = getNode(8); // Print the preorder traversal of the original tree System.out.print("Preorder Transversal before " + "modification of tree:\n"); preorderTraversal(root); replaceNodeWithSumUtil(root); // Print the preorder traversal of the modification // tree System.out.print("\nPreorder Transversal after " + "modification of tree:\n"); preorderTraversal(root); } } // This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach # Node of a binary tree class Node: def __init__(self, d): self.data = d self.left = None self.right = None # Function to store Preorder Traversal # of the binary tree in the vector V def StorePreorderTraversal(root): global v # If root is NULL, then return if (root == None): return # Store the root's data in V v.append(root.data) # Recur on the left subtree StorePreorderTraversal(root.left) # Recur on right subtree StorePreorderTraversal(root.right) # Function to replace each node of a # Binary Tree with the sum of its # preorder predecessor and successor def ReplaceNodeWithSum(root): global v, i # If root does not exist if (root == None): return # Update the data present in the # root by the sum of its preorder # predecessor and successor root.data = v[i - 1] + v[i + 1] # Increment index 'i' i += 1 # Recur on the left subtree ReplaceNodeWithSum(root.left) # Recur on the right subtree ReplaceNodeWithSum(root.right) # Utility function to replace each # node of a binary tree with the # sum of its preorder predecessor # and successor def ReplaceNodeWithSumUtil(root): global v, i # If tree is empty, then return if (root == None): return v.clear() # Stores the value of preorder # predecessor for root node v.append(0) # Store the preorder # traversal of the tree in V StorePreorderTraversal(root) # Store the value of preorder # successor for rightmost leaf v.append(0) # Replace each node # with the required sum i = 1 # Function call to update # the values of the node ReplaceNodeWithSum(root) # Function to print the preorder # traversal of a binary tree def PreorderTraversal(root): # If root is NULL if (root == None): return # Print the data of node print(root.data, end = " ") # Recur on the left subtree PreorderTraversal(root.left) # Recur on the right subtree PreorderTraversal(root.right) # Driver Code if __name__ == '__main__': # Binary Tree v, i = [], 0 root = Node(2) root.left = Node(3) root.right = Node(4) root.left.left = Node(6) root.left.right = Node(5) root.right.left = Node(7) root.right.right = Node(8) # Print the preorder traversal # of the original tree print("Preorder Traversal before " "modification of tree: ", end = "") PreorderTraversal(root) ReplaceNodeWithSumUtil(root) # Print the preorder traversal # of the modified tree print("\nPreorder Traversal after " "modification of tree: ", end = "") PreorderTraversal(root) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // TreeNode class class Node { public int data; public Node left, right; }; static int i; // Function to get a new node // of a binary tree static Node getNode(int data) { // Allocate node Node new_node = new Node(); // Put in the data; new_node.data = data; new_node.left = new_node.right = null; return new_node; } // Function to print the preorder traversal // of a binary tree static void preorderTraversal(Node root) { // If root is null if (root == null) return; // First print the data of node Console.Write(root.data + " "); // Then recur on left subtree preorderTraversal(root.left); // Now recur on right subtree preorderTraversal(root.right); } // Function to replace each node with the sum of its // preorder predecessor and successor static void replaceNodeWithSum(Node root, List<int> V) { // If root is null if (root == null) return; // Replace node's data with the sum of its // preorder predecessor and successor root.data = V[i - 1] + V[i + 1]; // Move 'i' to point to the next 'V' element i++; // First recur on left child replaceNodeWithSum(root.left, V); // Now recur on right child replaceNodeWithSum(root.right, V); } // Function to store the preorder traversal // of the binary tree in V static void storePreorderTraversal(Node root, List<int> V) { // If root is null if (root == null) return; // Then store the root's data in 'V' V.Add(root.data); // First recur on left child storePreorderTraversal(root.left, V); // Now recur on right child storePreorderTraversal(root.right, V); } // Utility function to replace each node in binary // tree with the sum of its preorder predecessor // and successor static void replaceNodeWithSumUtil(Node root) { // If tree is empty if (root == null) return; List<int> V = new List<int>(); // Store the value of preorder predecessor // for the leftmost leaf V.Add(0); // Store the preorder traversal of the tree in V storePreorderTraversal(root, V); // Store the value of preorder successor // for the rightmost leaf V.Add(0); // Replace each node with the required sum i = 1; replaceNodeWithSum(root, V); } static void Main() { // Binary tree formation Node root = getNode(2); root.left = getNode(3); root.right = getNode(4); root.left.left = getNode(6); root.left.right = getNode(5); root.right.left = getNode(7); root.right.right = getNode(8); // Print the preorder traversal of the original tree Console.Write("Preorder Transversal before " + "modification of tree: "); preorderTraversal(root); replaceNodeWithSumUtil(root); // Print the preorder traversal of the modification // tree Console.Write("\nPreorder Transversal after " + "modification of tree: "); preorderTraversal(root); } }
Javascript
<script> // Javascript program for the above approach class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to get a new node // of a binary tree function getNode(data) { // Allocate node let new_node = new Node(data); return new_node; } // Function to print the preorder traversal // of a binary tree function preorderTraversal(root) { // If root is null if (root == null) return; // First print the data of node document.write(root.data + " "); // Then recur on left subtree preorderTraversal(root.left); // Now recur on right subtree preorderTraversal(root.right); } // Function to replace each node with the sum of its // preorder predecessor and successor function replaceNodeWithSum(root, V) { // If root is null if (root == null) return; // Replace node's data with the sum of its // preorder predecessor and successor root.data = V[data - 1] + V[data + 1]; // Move 'i' to point to the next 'V' element data++; // First recur on left child replaceNodeWithSum(root.left, V); // Now recur on right child replaceNodeWithSum(root.right, V); } // Function to store the preorder traversal // of the binary tree in V function storePreorderTraversal(root, V) { // If root is null if (root == null) return; // Then store the root's data in 'V' V.push(root.data); // First recur on left child storePreorderTraversal(root.left, V); // Now recur on right child storePreorderTraversal(root.right, V); } // Utility function to replace each node in binary // tree with the sum of its preorder predecessor // and successor function replaceNodeWithSumUtil(root) { // If tree is empty if (root == null) return; let V = []; // Store the value of preorder predecessor // for the leftmost leaf V.push(0); // Store the preorder traversal of the tree in V storePreorderTraversal(root, V); // Store the value of preorder successor // for the rightmost leaf V.push(0); data = 1; replaceNodeWithSum(root, V); } // Binary tree formation let root = getNode(2); root.left = getNode(3); root.right = getNode(4); root.left.left = getNode(6); root.left.right = getNode(5); root.right.left = getNode(7); root.right.right = getNode(8); // Print the preorder traversal of the original tree document.write("Preorder Transversal before " + "modification of tree : "); preorderTraversal(root); replaceNodeWithSumUtil(root); // Print the preorder traversal of the modification // tree document.write("</br>" + "Preorder Transversal after " + "modification of tree : "); preorderTraversal(root); </script>
Preorder Traversal before modification of tree: 2 3 6 5 4 7 8 Preorder Traversal after modification of tree: 3 8 8 10 12 12 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)