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>
Producción:
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)