Dado un árbol binario que contiene n Nodes. El problema es reemplazar cada Node en el árbol binario con la suma de su predecesor en orden y su sucesor en orden.
Ejemplos:
Input : 1
/ \
2 3
/ \ / \
4 5 6 7
Output : 11
/ \
9 13
/ \ / \
2 3 4 3
For 1:
Inorder predecessor = 5
Inorder successor = 6
Sum = 11
For 4:
Inorder predecessor = 0
(as inorder predecessor is not present)
Inorder successor = 2
Sum = 2
For 7:
Inorder predecessor = 3
Inorder successor = 0
(as inorder successor is not present)
Sum = 3
Acercarse:
Crea una array arr . Almacene 0 en el índice 0. Ahora, almacene el recorrido en orden del árbol en la array arr . Luego, almacene 0 en el último índice. Los 0 se almacenan como el predecesor en orden de la hoja más a la izquierda y el sucesor en orden de la hoja más a la derecha no está presente. Ahora, realice un recorrido en orden y mientras recorre el Node reemplace el valor del Node con arr[i-1] + arr[i+1] y luego incremente i .
Al principio inicialice i = 1. Para un elemento arr[i] , los valores arr[i-1] y arr[i+1] son su predecesor en orden y su sucesor en orden respectivamente.
Implementación:
C++
// C++ implementation to replace each node
// in binary tree with the sum of its inorder
// predecessor and successor
#include <bits/stdc++.h>
using namespace std;
// node of a binary tree
struct Node {
int data;
struct Node* left, *right;
};
// function to get a new node of a binary tree
struct Node* getNode(int data)
{
// allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
// put in the data;
new_node->data = data;
new_node->left = new_node->right = NULL;
return new_node;
}
// function to store the inorder traversal
// of the binary tree in 'arr'
void storeInorderTraversal(struct Node* root,
vector<int>& arr)
{
// if root is NULL
if (!root)
return;
// first recur on left child
storeInorderTraversal(root->left, arr);
// then store the root's data in 'arr'
arr.push_back(root->data);
// now recur on right child
storeInorderTraversal(root->right, arr);
}
// function to replace each node with the sum of its
// inorder predecessor and successor
void replaceNodeWithSum(struct Node* root,
vector<int> arr, int* i)
{
// if root is NULL
if (!root)
return;
// first recur on left child
replaceNodeWithSum(root->left, arr, i);
// replace node's data with the sum of its
// inorder predecessor and successor
root->data = arr[*i - 1] + arr[*i + 1];
// move 'i' to point to the next 'arr' element
++*i;
// now recur on right child
replaceNodeWithSum(root->right, arr, i);
}
// Utility function to replace each node in binary
// tree with the sum of its inorder predecessor
// and successor
void replaceNodeWithSumUtil(struct Node* root)
{
// if tree is empty
if (!root)
return;
vector<int> arr;
// store the value of inorder predecessor
// for the leftmost leaf
arr.push_back(0);
// store the inorder traversal of the tree in 'arr'
storeInorderTraversal(root, arr);
// store the value of inorder successor
// for the rightmost leaf
arr.push_back(0);
// replace each node with the required sum
int i = 1;
replaceNodeWithSum(root, arr, &i);
}
// function to print the preorder traversal
// of a binary tree
void preorderTraversal(struct Node* root)
{
// if root is NULL
if (!root)
return;
// first print the data of node
cout << root->data << " ";
// then recur on left subtree
preorderTraversal(root->left);
// now recur on right subtree
preorderTraversal(root->right);
}
// Driver program to test above
int main()
{
// binary tree formation
struct Node* root = getNode(1); /* 1 */
root->left = getNode(2); /* / \ */
root->right = getNode(3); /* 2 3 */
root->left->left = getNode(4); /* / \ / \ */
root->left->right = getNode(5); /* 4 5 6 7 */
root->right->left = getNode(6);
root->right->right = getNode(7);
cout << "Preorder Traversal before tree modification:n";
preorderTraversal(root);
replaceNodeWithSumUtil(root);
cout << "\nPreorder Traversal after tree modification:n";
preorderTraversal(root);
return 0;
}
Java
// Java implementation to replace each node
// in binary tree with the sum of its inorder
// predecessor and successor
import java.util.*;
class Solution
{
// 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 store the inorder traversal
// of the binary tree in 'arr'
static void storeInorderTraversal( Node root,
Vector<Integer> arr)
{
// if root is null
if (root==null)
return;
// first recur on left child
storeInorderTraversal(root.left, arr);
// then store the root's data in 'arr'
arr.add(root.data);
// now recur on right child
storeInorderTraversal(root.right, arr);
}
// function to replace each node with the sum of its
// inorder predecessor and successor
static void replaceNodeWithSum( Node root,
Vector<Integer> arr, INT i)
{
// if root is null
if (root==null)
return;
// first recur on left child
replaceNodeWithSum(root.left, arr, i);
// replace node's data with the sum of its
// inorder predecessor and successor
root.data = arr.get(i.data - 1) + arr.get(i.data + 1);
// move 'i' to point to the next 'arr' element
i.data++;
// now recur on right child
replaceNodeWithSum(root.right, arr, i);
}
// Utility function to replace each node in binary
// tree with the sum of its inorder predecessor
// and successor
static void replaceNodeWithSumUtil( Node root)
{
// if tree is empty
if (root==null)
return;
Vector<Integer> arr= new Vector<Integer>();
// store the value of inorder predecessor
// for the leftmost leaf
arr.add(0);
// store the inorder traversal of the tree in 'arr'
storeInorderTraversal(root, arr);
// store the value of inorder successor
// for the rightmost leaf
arr.add(0);
// replace each node with the required sum
INT i = new INT();
i.data=1;
replaceNodeWithSum(root, arr, i);
}
// 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);
}
// Driver program to test above
public static void main(String args[])
{
// binary tree formation
Node root = getNode(1); // 1
root.left = getNode(2); // / \
root.right = getNode(3); // 2 3
root.left.left = getNode(4); // / \ / \
root.left.right = getNode(5); // 4 5 6 7
root.right.left = getNode(6);
root.right.right = getNode(7);
System.out.println( "Preorder Traversal before tree modification:");
preorderTraversal(root);
replaceNodeWithSumUtil(root);
System.out.println("\nPreorder Traversal after tree modification:");
preorderTraversal(root);
}
}
//contributed by Arnab Kundu
Python3
# Python3 implementation to replace each
# node in binary tree with the sum of its
# inorder predecessor and successor
# class to get a new node of a
# binary tree
class getNode:
def __init__(self, data):
# put in the data
self.data = data
self.left = self.right = None
# function to store the inorder traversal
# of the binary tree in 'arr'
def storeInorderTraversal(root, arr):
# if root is None
if (not root):
return
# first recur on left child
storeInorderTraversal(root.left, arr)
# then store the root's data in 'arr'
arr.append(root.data)
# now recur on right child
storeInorderTraversal(root.right, arr)
# function to replace each node with the
# sum of its inorder predecessor and successor
def replaceNodeWithSum(root, arr, i):
# if root is None
if (not root):
return
# first recur on left child
replaceNodeWithSum(root.left, arr, i)
# replace node's data with the sum of its
# inorder predecessor and successor
root.data = arr[i[0] - 1] + arr[i[0] + 1]
# move 'i' to point to the next 'arr' element
i[0] += 1
# now recur on right child
replaceNodeWithSum(root.right, arr, i)
# Utility function to replace each node in
# binary tree with the sum of its inorder
# predecessor and successor
def replaceNodeWithSumUtil(root):
# if tree is empty
if (not root):
return
arr = []
# store the value of inorder predecessor
# for the leftmost leaf
arr.append(0)
# store the inorder traversal of the
# tree in 'arr'
storeInorderTraversal(root, arr)
# store the value of inorder successor
# for the rightmost leaf
arr.append(0)
# replace each node with the required sum
i = [1]
replaceNodeWithSum(root, arr, i)
# function to print the preorder traversal
# of a binary tree
def preorderTraversal(root):
# if root is None
if (not root):
return
# first print the data of node
print(root.data, end = " ")
# then recur on left subtree
preorderTraversal(root.left)
# now recur on right subtree
preorderTraversal(root.right)
# Driver Code
if __name__ == '__main__':
# binary tree formation
root = getNode(1) # 1
root.left = getNode(2) # / \
root.right = getNode(3) # 2 3
root.left.left = getNode(4) # / \ / \
root.left.right = getNode(5) # 4 5 6 7
root.right.left = getNode(6)
root.right.right = getNode(7)
print("Preorder Traversal before",
"tree modification:")
preorderTraversal(root)
replaceNodeWithSumUtil(root)
print()
print("Preorder Traversal after",
"tree modification:")
preorderTraversal(root)
# This code is contributed by PranchalK
C#
// C# implementation to replace each
// node in binary tree with the sum
// of its inorder predecessor and successor
using System;
using System.Collections.Generic;
class GFG
{
// node of a binary tree
public class Node
{
public int data;
public Node left, right;
}
// INT class
public class INT
{
public int data;
}
// function to get a new node
// of a binary tree
public 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 store the inorder traversal
// of the binary tree in 'arr'
public static void storeInorderTraversal(Node root,
List<int> arr)
{
// if root is null
if (root == null)
{
return;
}
// first recur on left child
storeInorderTraversal(root.left, arr);
// then store the root's data in 'arr'
arr.Add(root.data);
// now recur on right child
storeInorderTraversal(root.right, arr);
}
// function to replace each node with
// the sum of its inorder predecessor
// and successor
public static void replaceNodeWithSum(Node root,
List<int> arr, INT i)
{
// if root is null
if (root == null)
{
return;
}
// first recur on left child
replaceNodeWithSum(root.left, arr, i);
// replace node's data with the
// sum of its inorder predecessor
// and successor
root.data = arr[i.data - 1] + arr[i.data + 1];
// move 'i' to point to the
// next 'arr' element
i.data++;
// now recur on right child
replaceNodeWithSum(root.right, arr, i);
}
// Utility function to replace each
// node in binary tree with the sum
// of its inorder predecessor and successor
public static void replaceNodeWithSumUtil(Node root)
{
// if tree is empty
if (root == null)
{
return;
}
List<int> arr = new List<int>();
// store the value of inorder
// predecessor for the leftmost leaf
arr.Add(0);
// store the inorder traversal
// of the tree in 'arr'
storeInorderTraversal(root, arr);
// store the value of inorder successor
// for the rightmost leaf
arr.Add(0);
// replace each node with
// the required sum
INT i = new INT();
i.data = 1;
replaceNodeWithSum(root, arr, i);
}
// function to print the preorder
// traversal of a binary tree
public 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);
}
// Driver Code
public static void Main(string[] args)
{
// binary tree formation
Node root = getNode(1); // 1
root.left = getNode(2); // / \
root.right = getNode(3); // 2 3
root.left.left = getNode(4); // / \ / \
root.left.right = getNode(5); // 4 5 6 7
root.right.left = getNode(6);
root.right.right = getNode(7);
Console.WriteLine("Preorder Traversal " +
"before tree modification:");
preorderTraversal(root);
replaceNodeWithSumUtil(root);
Console.WriteLine("\nPreorder Traversal after " +
"tree modification:");
preorderTraversal(root);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript implementation to replace each node
// in binary tree with the sum of its inorder
// predecessor and successor
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 store the inorder traversal
// of the binary tree in 'arr'
function storeInorderTraversal(root, arr)
{
// If root is null
if (root == null)
return;
// First recur on left child
storeInorderTraversal(root.left, arr);
// then store the root's data in 'arr'
arr.push(root.data);
// Now recur on right child
storeInorderTraversal(root.right, arr);
}
// Function to replace each node with the
// sum of its inorder predecessor and successor
function replaceNodeWithSum(root, arr)
{
// If root is null
if (root == null)
return;
// First recur on left child
replaceNodeWithSum(root.left, arr);
// Replace node's data with the sum of its
// inorder predecessor and successor
root.data = arr[data - 1] + arr[data + 1];
// Move 'i' to point to the next 'arr' element
data++;
// Now recur on right child
replaceNodeWithSum(root.right, arr);
}
// Utility function to replace each node in binary
// tree with the sum of its inorder predecessor
// and successor
function replaceNodeWithSumUtil(root)
{
// If tree is empty
if (root == null)
return;
let arr = [];
// Store the value of inorder predecessor
// for the leftmost leaf
arr.push(0);
// Store the inorder traversal of
// the tree in 'arr'
storeInorderTraversal(root, arr);
// Store the value of inorder successor
// for the rightmost leaf
arr.push(0);
// Replace each node with the required sum
data = 1;
replaceNodeWithSum(root, arr);
}
// 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);
}
// Driver code
// Binary tree formation
let root = getNode(1); // 1
root.left = getNode(2); // / \
root.right = getNode(3); // 2 3
root.left.left = getNode(4); // / \ / \
root.left.right = getNode(5); // 4 5 6 7
root.right.left = getNode(6);
root.right.right = getNode(7);
document.write("Preorder Traversal before " +
"tree modification:" + "</br>");
preorderTraversal(root);
replaceNodeWithSumUtil(root);
document.write("</br>" + "Preorder Traversal after " +
"tree modification:" + "</br>");
preorderTraversal(root);
// This code is contributed by divyeshrabadiya07
</script>
Producción
Preorder Traversal before tree modification:n1 2 4 5 3 6 7 Preorder Traversal after tree modification:n11 9 2 3 13 4 3
Complejidad de tiempo: O (n) , ya que estamos atravesando el árbol que tiene n Nodes usando recursividad (recorrido en orden previo y en orden).
Espacio auxiliar: O(n), ya que estamos usando espacio adicional para almacenar el recorrido en orden.
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Otro enfoque (sin vector extra):
- Use el recorrido en orden y mantenga el Node anterior y el valor del Node anterior anterior.
- Actualizar el Node anterior con el Node actual + el valor anterior del anterior
Implementación:
C++
// C++ implementation to replace each node
// in binary tree with the sum of its inorder
// predecessor and successor
#include <bits/stdc++.h>
using namespace std;
// node of a binary tree
struct Node {
int data;
struct Node* left, *right;
};
// function to get a new node of a binary tree
struct Node* getNode(int data)
{
// allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct 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
void preorderTraversal(struct Node* root)
{
// if root is NULL
if (!root)
return;
// first print the data of node
cout << root->data << " ";
// then recur on left subtree
preorderTraversal(root->left);
// now recur on right subtree
preorderTraversal(root->right);
}
void inOrderTraverse(struct Node* root, struct Node* &prev, int &prevVal)
{
if(root == NULL) return;
inOrderTraverse(root->left, prev, prevVal);
if(prev == NULL)
{
prev = root;
prevVal = 0;
}
else
{
int temp = prev->data;
prev->data = prevVal + root->data;
prev = root;
prevVal = temp;
}
inOrderTraverse(root->right, prev, prevVal);
}
// Driver program to test above
int main()
{
// binary tree formation
struct Node* root = getNode(1); /* 1 */
root->left = getNode(2); /* / \ */
root->right = getNode(3); /* 2 3 */
root->left->left = getNode(4); /* / \ / \ */
root->left->right = getNode(5); /* 4 5 6 7 */
root->right->left = getNode(6);
root->right->right = getNode(7);
cout << "Preorder Traversal before tree modification:\n";
preorderTraversal(root);
struct Node* prev = NULL;
int prevVal = -1;
inOrderTraverse(root, prev, prevVal);
// update righmost node.
prev->data = prevVal;
cout << "\nPreorder Traversal after tree modification:\n";
preorderTraversal(root);
return 0;
}
C#
// C# implementation to replace each node
// in binary tree with the sum of its inorder
// predecessor and successor
using System;
using System.Collections.Generic;
class GFG {
// node of a binary tree
public class Node {
public int data;
public Node left, right;
}
// function to get a new node
// of a binary tree
public 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
public 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);
}
public static void inOrderTraverse(Node root,
ref Node prev,
ref int prevVal)
{
if (root == null)
return;
inOrderTraverse(root.left, ref prev, ref prevVal);
if (prev == null) {
prev = root;
prevVal = 0;
}
else {
int temp = prev.data;
prev.data = prevVal + root.data;
prev = root;
prevVal = temp;
}
inOrderTraverse(root.right, ref prev, ref prevVal);
}
// Driver Code
public static void Main(string[] args)
{
// binary tree formation
Node root = getNode(1); // 1
root.left = getNode(2); // / \
root.right = getNode(3); // 2 3
root.left.left = getNode(4); // / \ / \
root.left.right = getNode(5); // 4 5 6 7
root.right.left = getNode(6);
root.right.right = getNode(7);
Console.WriteLine("Preorder Traversal "
+ "before tree modification:");
preorderTraversal(root);
Node prev = null;
int prevVal = -1;
inOrderTraverse(root, ref prev, ref prevVal);
// update righmost node.
prev.data = prevVal;
Console.WriteLine("\nPreorder Traversal after "
+ "tree modification:");
preorderTraversal(root);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
Preorder Traversal before tree modification: 1 2 4 5 3 6 7 Preorder Traversal after tree modification: 11 9 2 3 13 4 3
Complejidad de tiempo: O (n) , ya que estamos atravesando el árbol que tiene n Nodes usando recursividad.
Espacio auxiliar: O(n) , no estamos usando ningún espacio explícito, pero como estamos usando la recursividad, habrá sp extra debido al espacio recursivo de la pila.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA