Dado un árbol N -ario . La tarea es reemplazar los valores de cada Node con la suma de todos sus subárboles y el propio Node .
Ejemplos
Entrada: 1
/ | \
2 3 4
/ \ \
5 6 7
Salida: Recorrido de pedido anticipado inicial: 1 2 5 6 7 3 4
Recorrido de pedido anticipado final: 28 20 5 6 7 3 4
Explicación: El valor de cada Node se reemplaza por la suma de todos sus subárboles y el propio Node.Entrada: 1
/ | \
4 2 3
/ \ \
7 6 5
Salida: Recorrido inicial de pedido anticipado: 1 4 7 6 3 5
Recorrido final de pedido anticipado: 23 13 7 6 28 5
Enfoque: Este problema se puede resolver usando Recursion . Siga los pasos a continuación para resolver el problema dado.
- La forma más fácil de resolver este problema es mediante recursividad .
- Comience con la condición base cuando el Node actual sea igual a NULL y luego devuelva 0 , ya que significa que es el Node hoja.
- De lo contrario, realice una llamada recursiva a todos sus Nodes secundarios atravesando mediante un bucle y agregue la suma de todos los Nodes secundarios en él.
- Por último, devuelve los datos del Node actual.
- De esta forma, todos los valores del Node serán reemplazados por la suma de todos los subárboles y él mismo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Class for the node of the tree
struct Node {
int data;
// List of children
struct Node** children;
int length;
Node()
{
length = 0;
data = 0;
}
Node(int n, int data_)
{
children = new Node*();
length = n;
data = data_;
}
};
// Function to replace node with
// sum of its left subtree, right
// subtree and its sum
int sumReplacementNary(Node* node)
{
if (node == NULL)
return 0;
// Total children count
int total = node->length;
// Taking sum of all the nodes
for (int i = 0; i < total; i++)
node->data += sumReplacementNary(node->children[i]);
return node->data;
}
void preorderTraversal(Node* node)
{
if (node == NULL)
return;
// Total children count
int total = node->length;
// Print the current node's data
cout << node->data << " ";
// All the children except the last
for (int i = 0; i < total - 1; i++)
preorderTraversal(node->children[i]);
// Last child
preorderTraversal(node->children[total - 1]);
}
// Driver code
int main()
{
/* Create the following tree
1
/ | \
2 3 4
/ \ \
5 6 7
*/
int N = 3;
Node* root = new Node(N, 1);
root->children[0] = new Node(N, 2);
root->children[1] = new Node(N, 3);
root->children[2] = new Node(N, 4);
root->children[0]->children[0] = new Node(N, 5);
root->children[0]->children[1] = new Node(N, 6);
root->children[0]->children[2] = new Node(N, 7);
cout << "Initial Pre-order Traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Final Pre-order Traversal: ";
sumReplacementNary(root);
preorderTraversal(root);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG{
// Class for the node of the tree
static class Node {
int data;
// List of children
Node []children;
int length;
Node()
{
length = 0;
data = 0;
}
Node(int n, int data_)
{
children = new Node[n];
length = n;
data = data_;
}
};
// Function to replace node with
// sum of its left subtree, right
// subtree and its sum
static int sumReplacementNary(Node node)
{
if (node == null)
return 0;
// Total children count
int total = node.length;
// Taking sum of all the nodes
for (int i = 0; i < total; i++)
node.data += sumReplacementNary(node.children[i]);
return node.data;
}
static void preorderTraversal(Node node)
{
if (node == null)
return;
// Total children count
int total = node.length;
// Print the current node's data
System.out.print(node.data+ " ");
// All the children except the last
for (int i = 0; i < total - 1; i++)
preorderTraversal(node.children[i]);
// Last child
preorderTraversal(node.children[total - 1]);
}
// Driver code
public static void main(String[] args)
{
/* Create the following tree
1
/ | \
2 3 4
/ \ \
5 6 7
*/
int N = 3;
Node root = new Node(N, 1);
root.children[0] = new Node(N, 2);
root.children[1] = new Node(N, 3);
root.children[2] = new Node(N, 4);
root.children[0].children[0] = new Node(N, 5);
root.children[0].children[1] = new Node(N, 6);
root.children[0].children[2] = new Node(N, 7);
System.out.print("Initial Pre-order Traversal: ");
preorderTraversal(root);
System.out.println();
System.out.print("Final Pre-order Traversal: ");
sumReplacementNary(root);
preorderTraversal(root);
}
}
Python3
# Python implementation of the approach
# Class for the node of the tree
class Node:
def __init__(self, data):
self.data = data
self.children = []
# Function to replace node with
# sum of its left subtree, right
# subtree and its sum
def sumReplacementNary(node):
if (node == None):
return 0
# Total children count
total = len(node.children)
# Taking sum of all the nodes
for i in range(0, total):
node.data += sumReplacementNary(node.children[i])
return node.data
def preorderTraversal(node):
if (node == None):
return
# Total children count
total = len(node.children)
# Print the current node's data
print(node.data, end=" ")
# All the children except the last
for i in range(0, total):
preorderTraversal(node.children[i])
# Driver code
# Create the following tree
# 1
# / | \
# 2 3 4
# / \ \
# 5 6 7
root = Node(1)
root.children.append(Node(2))
root.children.append(Node(3))
root.children.append(Node(4))
root.children[0].children.append(Node(5))
root.children[0].children.append(Node(6))
root.children[0].children.append(Node(7))
print("Initial Pre-order Traversal: ")
preorderTraversal(root)
print("\n")
print("Final Pre-order Traversal: ")
sumReplacementNary(root)
preorderTraversal(root)
C#
// C# implementation of the approach
using System;
public class GFG{
// Class for the node of the tree
class Node {
public int data;
// List of children
public Node []children;
public int length;
public Node()
{
length = 0;
data = 0;
}
public Node(int n, int data_)
{
children = new Node[n];
length = n;
data = data_;
}
};
// Function to replace node with
// sum of its left subtree, right
// subtree and its sum
static int sumReplacementNary(Node node)
{
if (node == null)
return 0;
// Total children count
int total = node.length;
// Taking sum of all the nodes
for (int i = 0; i < total; i++)
node.data += sumReplacementNary(node.children[i]);
return node.data;
}
static void preorderTraversal(Node node)
{
if (node == null)
return;
// Total children count
int total = node.length;
// Print the current node's data
Console.Write(node.data+ " ");
// All the children except the last
for (int i = 0; i < total - 1; i++)
preorderTraversal(node.children[i]);
// Last child
preorderTraversal(node.children[total - 1]);
}
// Driver code
public static void Main(String[] args)
{
/* Create the following tree
1
/ | \
2 3 4
/ \ \
5 6 7
*/
int N = 3;
Node root = new Node(N, 1);
root.children[0] = new Node(N, 2);
root.children[1] = new Node(N, 3);
root.children[2] = new Node(N, 4);
root.children[0].children[0] = new Node(N, 5);
root.children[0].children[1] = new Node(N, 6);
root.children[0].children[2] = new Node(N, 7);
Console.Write("Initial Pre-order Traversal: ");
preorderTraversal(root);
Console.WriteLine();
Console.Write("Final Pre-order Traversal: ");
sumReplacementNary(root);
preorderTraversal(root);
}
}
Javascript
<script>
// JavaScript code for the above approach
// Class for the node of the tree
class Node {
// List of children
constructor(n = 0, data_ = 0) {
this.children = new Array(10000);
this.length = n;
this.data = data_;
}
}
// Function to replace node with
// sum of its left subtree, right
// subtree and its sum
function sumReplacementNary(node) {
if (node == null)
return 0;
// Total children count
let total = node.length;
// Taking sum of all the nodes
for (let i = 0; i < total; i++)
node.data += sumReplacementNary(node.children[i]);
return node.data;
}
function preorderTraversal(node) {
if (node == null)
return;
// Total children count
let total = node.length;
// Print the current node's data
document.write(node.data + " ");
// All the children except the last
for (let i = 0; i < total - 1; i++)
preorderTraversal(node.children[i]);
// Last child
preorderTraversal(node.children[total - 1]);
}
// Driver code
/* Create the following tree
1
/ | \
2 3 4
/ \ \
5 6 7
*/
let N = 3;
let root = new Node(N, 1);
root.children[0] = new Node(N, 2);
root.children[1] = new Node(N, 3);
root.children[2] = new Node(N, 4);
root.children[0].children[0] = new Node(N, 5);
root.children[0].children[1] = new Node(N, 6);
root.children[0].children[2] = new Node(N, 7);
document.write("Initial Pre-order Traversal: ");
preorderTraversal(root);
document.write('<br>')
document.write("Final Pre-order Traversal: ");
sumReplacementNary(root);
preorderTraversal(root);
</script>
Producción
Initial Pre-order Traversal: 1 2 5 6 7 3 4 Final Pre-order Traversal: 28 20 5 6 7 3 4
Complejidad temporal: O(N), donde N es el número de Nodes del árbol.
Publicación traducida automáticamente
Artículo escrito por refertoyash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA