Dada una array pre[] , que representa el recorrido Preorder de un Perfect Binary Tree que consta de N Nodes, la tarea es construir un Perfect Binary Tree a partir del Preorder Traversal dado y devolver la raíz del árbol.
Ejemplos:
Entrada: pre[] = {1, 2, 4, 5, 3, 6, 7}
Salida:
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7Entrada: pre[] = {1, 2, 3}
Salida:
1
/ \
/ \
2 3
En general, para construir un árbol binario, no podemos hacerlo usando solo el recorrido de orden previo, pero aquí se da una condición adicional de que el árbol binario es un árbol binario perfecto. Podemos usar esa condición extra.
Para el árbol binario perfecto, cada Node tiene 2 o 0 hijos, y todos los Nodes hoja están presentes en el mismo nivel. Y el recorrido en preorden de un árbol binario contiene primero la raíz, luego el recorrido en preorden del subárbol izquierdo, luego el recorrido en preorden del subárbol derecho. Entonces, para el árbol binario perfecto, la raíz debe tener el mismo número de hijos en ambos subárboles, por lo que el número (digamos, n) de elementos después de la raíz en el recorrido de preorden debe ser par (2 * número de Nodes en un subárbol, ya que es perfecto árbol binario) . Y dado que cada subárbol tiene el mismo número de Nodes para el árbol binario perfecto, podemos encontrar el recorrido en orden previo del subárbol izquierdo (que es la mitad de la array después de la raíz en el recorrido en orden previo de todo el árbol),
Entonces, el primer elemento en el recorrido preordenado es la raíz, construiremos un Node como la raíz con este elemento, luego podemos encontrar fácilmente los recorridos preordenados de los subárboles izquierdo y derecho de la raíz, y construiremos recursivamente los subárboles izquierdo y derecho. subárboles derechos de la raíz.
Enfoque: El problema dado se puede resolver usando recursividad . Siga los pasos a continuación para resolver el problema:
- Cree una función, digamos BuildPerfectBT_helper con parámetros como preStart , preEnd , pre[] donde preStart representa el índice inicial de la array pre[] y preEnd representa el índice final de la array pre[] y realiza los siguientes pasos:
- Si el valor de preStart es mayor que preEnd , devuelve NULL .
- Inicialice la raíz como pre[preStart] .
- Si el valor de preStart es el mismo que el de preEnd , devuelva root .
- Inicialice 4 variables, digamos leftPreStart como preStart + 1 , rightPreStart como leftPreStart + (preEnd – leftPreStart+1)/2 , leftPreEnd como rightPreStart – 1 y rightPreEnd como preEnd .
- Modifique el valor de root->left llamando recursivamente a la función buildPerfectBT_helper() con los parámetros leftPreStart , leftPreEnd y pre[] .
- Modifique el valor de root->right llamando recursivamente a la función buildPerfectBT_helper() con los parámetros rightPreStart , rightPreEnd y pre[] .
- Después de realizar los pasos anteriores, devuelva root .
- Después de crear el árbol binario perfecto, imprima el recorrido en orden del árbol .
A continuación se muestra la ilustración de los pasos anteriores discutidos:
Paso 1: construir ([1, 2, 4, 5, 3, 6, 7])
Paso 2:
1
/ \
/ \
construir ([2, 4, 5]) construir ([3, 6, 7])Ahora, el primer elemento (1 aquí) es raíz, luego el subarreglo después del primer elemento (que es [2,4,5,3,6,7] aquí) contiene los recorridos preordenados de los subárboles izquierdo y derecho. Y sabemos que el recorrido en preorden del subárbol izquierdo es la primera mitad, es decir, [2,4,5], y el recorrido en preorden del subárbol derecho es la segunda mitad, es decir, [3,6,7]. Ahora construya recursivamente los subárboles izquierdo y derecho.
Paso 3:
1___________|_________________
/ \
/ \
2 3
______/___________ _______\____________
/ \ / \
/ \ / \
build([4]) build([5]) build([6]) build([7])
Paso 4:
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
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;
// Structure of the tree
struct Node {
int data;
Node *left, *right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
// Function to create a new node with
// the value val
Node* getNewNode(int val)
{
Node* newNode = new Node(val);
newNode->data = val;
newNode->left = newNode->right = NULL;
// Return the newly created node
return newNode;
}
// Function to create the Perfect
// Binary Tree
Node* buildPerfectBT_helper(int preStart,
int preEnd,
int pre[])
{
// If preStart > preEnd return NULL
if (preStart > preEnd)
return NULL;
// Initialize root as pre[preStart]
Node* root = getNewNode(pre[preStart]);
;
// If the only node is left,
// then return node
if (preStart == preEnd)
return root;
// Parameters for further recursion
int leftPreStart = preStart + 1;
int rightPreStart = leftPreStart
+ (preEnd - leftPreStart + 1) / 2;
int leftPreEnd = rightPreStart - 1;
int rightPreEnd = preEnd;
// Recursive Call to build the
// subtree of root node
root->left = buildPerfectBT_helper(
leftPreStart, leftPreEnd, pre);
root->right = buildPerfectBT_helper(
rightPreStart, rightPreEnd, pre);
// Return the created root
return root;
}
// Function to build Perfect Binary Tree
Node* buildPerfectBT(int pre[], int size)
{
return buildPerfectBT_helper(0, size - 1, pre);
}
// Function to print the Inorder of
// the given Tree
void printInorder(Node* root)
{
// Base Case
if (!root)
return;
// Left Recursive Call
printInorder(root->left);
// Print the data
cout << root->data << " ";
// Right Recursive Call
printInorder(root->right);
}
// Driver Code
int main()
{
int pre[] = { 1, 2, 4, 5, 3, 6, 7 };
int N = sizeof(pre) / sizeof(pre[0]);
// Function Call
Node* root = buildPerfectBT(pre, N);
// Print Inorder Traversal
cout << "\nInorder traversal of the tree: ";
printInorder(root);
return 0;
}
Java
// Java program for the above approach
public class Main
{
// Structure of the tree
static class Node {
public int data;
public Node left, right;
public Node(int val)
{
data = val;
left = right = null;
}
}
// Function to create a new node with
// the value val
static Node getNewNode(int val)
{
Node newNode = new Node(val);
// Return the newly created node
return newNode;
}
// Function to create the Perfect
// Binary Tree
static Node buildPerfectBT_helper(int preStart, int preEnd, int[] pre)
{
// If preStart > preEnd return NULL
if (preStart > preEnd)
return null;
// Initialize root as pre[preStart]
Node root = getNewNode(pre[preStart]);
// If the only node is left,
// then return node
if (preStart == preEnd)
return root;
// Parameters for further recursion
int leftPreStart = preStart + 1;
int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2;
int leftPreEnd = rightPreStart - 1;
int rightPreEnd = preEnd;
// Recursive Call to build the
// subtree of root node
root.left = buildPerfectBT_helper(
leftPreStart, leftPreEnd, pre);
root.right = buildPerfectBT_helper(
rightPreStart, rightPreEnd, pre);
// Return the created root
return root;
}
// Function to build Perfect Binary Tree
static Node buildPerfectBT(int[] pre, int size)
{
return buildPerfectBT_helper(0, size - 1, pre);
}
// Function to print the Inorder of
// the given Tree
static void printInorder(Node root)
{
// Base Case
if (root == null)
return;
// Left Recursive Call
printInorder(root.left);
// Print the data
System.out.print(root.data + " ");
// Right Recursive Call
printInorder(root.right);
}
public static void main(String[] args) {
int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
int N = pre.length;
// Function Call
Node root = buildPerfectBT(pre, N);
// Print Inorder Traversal
System.out.print("Inorder traversal of the tree: ");
printInorder(root);
}
}
// This code is contributed by suresh07.
Python3
# Python3 program for the above approach
# Structure of the tree
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
# Function to create a new node with
# the value val
def getNewNode(val):
newNode = Node(val)
# Return the newly created node
return newNode
# Function to create the Perfect
# Binary Tree
def buildPerfectBT_helper(preStart, preEnd, pre):
# If preStart > preEnd return NULL
if (preStart > preEnd):
return None
# Initialize root as pre[preStart]
root = getNewNode(pre[preStart])
# If the only node is left,
# then return node
if (preStart == preEnd):
return root
# Parameters for further recursion
leftPreStart = preStart + 1
rightPreStart = leftPreStart + int((preEnd - leftPreStart + 1) / 2)
leftPreEnd = rightPreStart - 1
rightPreEnd = preEnd
# Recursive Call to build the
# subtree of root node
root.left = buildPerfectBT_helper(leftPreStart, leftPreEnd, pre)
root.right = buildPerfectBT_helper(rightPreStart, rightPreEnd, pre)
# Return the created root
return root
# Function to build Perfect Binary Tree
def buildPerfectBT(pre, size):
return buildPerfectBT_helper(0, size - 1, pre)
# Function to print the Inorder of
# the given Tree
def printInorder(root):
# Base Case
if (root == None):
return
# Left Recursive Call
printInorder(root.left)
# Print the data
print(root.data, "", end = "")
# Right Recursive Call
printInorder(root.right)
pre = [ 1, 2, 4, 5, 3, 6, 7 ]
N = len(pre)
# Function Call
root = buildPerfectBT(pre, N)
# Print Inorder Traversal
print("Inorder traversal of the tree: ", end = "")
printInorder(root)
# This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Structure of the tree
class Node {
public int data;
public Node left, right;
public Node(int val)
{
data = val;
left = right = null;
}
}
// Function to create a new node with
// the value val
static Node getNewNode(int val)
{
Node newNode = new Node(val);
// Return the newly created node
return newNode;
}
// Function to create the Perfect
// Binary Tree
static Node buildPerfectBT_helper(int preStart, int preEnd, int[] pre)
{
// If preStart > preEnd return NULL
if (preStart > preEnd)
return null;
// Initialize root as pre[preStart]
Node root = getNewNode(pre[preStart]);
// If the only node is left,
// then return node
if (preStart == preEnd)
return root;
// Parameters for further recursion
int leftPreStart = preStart + 1;
int rightPreStart = leftPreStart + (preEnd - leftPreStart + 1) / 2;
int leftPreEnd = rightPreStart - 1;
int rightPreEnd = preEnd;
// Recursive Call to build the
// subtree of root node
root.left = buildPerfectBT_helper(
leftPreStart, leftPreEnd, pre);
root.right = buildPerfectBT_helper(
rightPreStart, rightPreEnd, pre);
// Return the created root
return root;
}
// Function to build Perfect Binary Tree
static Node buildPerfectBT(int[] pre, int size)
{
return buildPerfectBT_helper(0, size - 1, pre);
}
// Function to print the Inorder of
// the given Tree
static void printInorder(Node root)
{
// Base Case
if (root == null)
return;
// Left Recursive Call
printInorder(root.left);
// Print the data
Console.Write(root.data + " ");
// Right Recursive Call
printInorder(root.right);
}
static void Main() {
int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
int N = pre.Length;
// Function Call
Node root = buildPerfectBT(pre, N);
// Print Inorder Traversal
Console.Write("Inorder traversal of the tree: ");
printInorder(root);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program for the above approach
// Structure of the tree
class Node
{
constructor(val) {
this.left = null;
this.right = null;
this.data = val;
}
}
// Function to create a new node with
// the value val
function getNewNode(val)
{
let newNode = new Node(val);
// Return the newly created node
return newNode;
}
// Function to create the Perfect
// Binary Tree
function buildPerfectBT_helper(preStart, preEnd, pre)
{
// If preStart > preEnd return NULL
if (preStart > preEnd)
return null;
// Initialize root as pre[preStart]
let root = getNewNode(pre[preStart]);
// If the only node is left,
// then return node
if (preStart == preEnd)
return root;
// Parameters for further recursion
let leftPreStart = preStart + 1;
let rightPreStart = leftPreStart
+ parseInt((preEnd - leftPreStart + 1) / 2);
let leftPreEnd = rightPreStart - 1;
let rightPreEnd = preEnd;
// Recursive Call to build the
// subtree of root node
root.left = buildPerfectBT_helper(
leftPreStart, leftPreEnd, pre);
root.right = buildPerfectBT_helper(
rightPreStart, rightPreEnd, pre);
// Return the created root
return root;
}
// Function to build Perfect Binary Tree
function buildPerfectBT(pre, size)
{
return buildPerfectBT_helper(0, size - 1, pre);
}
// Function to print the Inorder of
// the given Tree
function printInorder(root)
{
// Base Case
if (root == null)
return;
// Left Recursive Call
printInorder(root.left);
// Print the data
document.write(root.data + " ");
// Right Recursive Call
printInorder(root.right);
}
let pre = [ 1, 2, 4, 5, 3, 6, 7 ];
let N = pre.length;
// Function Call
let root = buildPerfectBT(pre, N);
// Print Inorder Traversal
document.write("Inorder traversal of the tree: ");
printInorder(root);
// This code is contributed by divyesh072019.
</script>
Inorder traversal of the tree: 4 2 5 1 6 3 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourashis69 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA