Dados los recorridos Postorder e Inorder, construya el árbol.
Ejemplos:
Input:
in[] = {2, 1, 3}
post[] = {2, 3, 1}
Output: Root of below tree
1
/ \
2 3
Input:
in[] = {4, 8, 2, 5, 1, 6, 3, 7}
post[] = {8, 4, 5, 2, 6, 7, 3, 1}
Output: Root of below tree
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Ya hemos discutido la construcción de árboles a partir de recorridos Inorder y Preorder . La idea es parecida.
Veamos el proceso de construcción del árbol desde in[] = {4, 8, 2, 5, 1, 6, 3, 7} y post[] = {8, 4, 5, 2, 6, 7, 3, 1}
1) Primero buscamos el último Node en post[]. El último Node es «1», sabemos que este valor es raíz ya que la raíz siempre aparece al final del recorrido posterior al pedido.
2) Buscamos «1» en in[] para encontrar los subárboles izquierdo y derecho de la raíz. Todo lo que está a la izquierda de «1» en in[] está en el subárbol izquierdo y todo lo que está a la derecha está en el subárbol derecho.
1
/ \
[4, 8, 2, 5] [6, 3, 7]
3) Repetimos el proceso anterior para los dos siguientes.
…. b) Repetir para in[] = {6, 3, 7} y post[] = {6, 7, 3}
…….Hacer que el árbol creado sea el hijo derecho de la raíz.
…. a) Repetir para in[] = {4, 8, 2, 5} y post[] = {8, 4, 5, 2}.
…….Haga que el árbol creado sea el hijo izquierdo de la raíz.
A continuación se muestra la implementación de la idea anterior. Una observación importante es que llamamos recursivamente al subárbol derecho antes del subárbol izquierdo a medida que disminuimos el índice del índice posterior al pedido cada vez que creamos un nuevo Node.
C++
/* C++ program to construct tree using inorder and
postorder traversals */
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left
child and a pointer to right child */
struct Node {
int data;
Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int data);
/* Prototypes for utility functions */
int search(int arr[], int strt, int end, int value);
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
Node* buildUtil(int in[], int post[], int inStrt,
int inEnd, int* pIndex)
{
// Base case
if (inStrt > inEnd)
return NULL;
/* Pick current node from Postorder traversal using
postIndex and decrement postIndex */
Node* node = newNode(post[*pIndex]);
(*pIndex)--;
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
/* Else find the index of this node in Inorder
traversal */
int iIndex = search(in, inStrt, inEnd, node->data);
/* Using index in Inorder traversal, construct left and
right subtress */
node->right = buildUtil(in, post, iIndex + 1, inEnd, pIndex);
node->left = buildUtil(in, post, inStrt, iIndex - 1, pIndex);
return node;
}
// This function mainly initializes index of root
// and calls buildUtil()
Node* buildTree(int in[], int post[], int n)
{
int pIndex = n - 1;
return buildUtil(in, post, 0, n - 1, &pIndex);
}
/* Function to find index of value in arr[start...end]
The function assumes that value is postsent in in[] */
int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
break;
}
return i;
}
/* Helper function that allocates a new node */
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
/* This function is here just to test */
void preOrder(Node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
// Driver code
int main()
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = sizeof(in) / sizeof(in[0]);
Node* root = buildTree(in, post, n);
cout << "Preorder of the constructed tree : \n";
preOrder(root);
return 0;
}
Java
// Java program to construct a tree using inorder
// and postorder traversals
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class Node {
int data;
Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
class BinaryTree {
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
Node buildUtil(int in[], int post[], int inStrt,
int inEnd, int postStrt, int postEnd)
{
// Base case
if (inStrt > inEnd)
return null;
/* Pick current node from Postorder traversal using
postIndex and decrement postIndex */
Node node = new Node(post[postEnd]);
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
int iIndex = search(in, inStrt, inEnd, node.data);
/* Using index in Inorder traversal, construct left
and right subtress */
node.left = buildUtil(
in, post, inStrt, iIndex - 1, postStrt,
postStrt - inStrt + iIndex - 1);
node.right = buildUtil(in, post, iIndex + 1, inEnd,
postEnd - inEnd + iIndex,
postEnd - 1);
return node;
}
/* Function to find index of value in arr[start...end]
The function assumes that value is postsent in in[]
*/
int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
break;
}
return i;
}
/* This function is here just to test */
void preOrder(Node node)
{
if (node == null)
return;
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver Code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
int in[] = new int[] { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = new int[] { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = in.length;
Node root
= tree.buildUtil(in, post, 0, n - 1, 0, n - 1);
System.out.println(
"Preorder of the constructed tree : ");
tree.preOrder(root);
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)
Python3
# Python3 program to construct tree using
# inorder and postorder traversals
# Helper function that allocates
# a new node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Recursive function to construct binary
# of size n from Inorder traversal in[]
# and Postorder traversal post[]. Initial
# values of inStrt and inEnd should be
# 0 and n -1. The function doesn't do any
# error checking for cases where inorder
# and postorder do not form a tree
def buildUtil(In, post, inStrt, inEnd, pIndex):
# Base case
if (inStrt > inEnd):
return None
# Pick current node from Postorder traversal
# using postIndex and decrement postIndex
node = newNode(post[pIndex[0]])
pIndex[0] -= 1
# If this node has no children
# then return
if (inStrt == inEnd):
return node
# Else find the index of this node
# in Inorder traversal
iIndex = search(In, inStrt, inEnd, node.data)
# Using index in Inorder traversal,
# construct left and right subtress
node.right = buildUtil(In, post, iIndex + 1,
inEnd, pIndex)
node.left = buildUtil(In, post, inStrt,
iIndex - 1, pIndex)
return node
# This function mainly initializes index
# of root and calls buildUtil()
def buildTree(In, post, n):
pIndex = [n - 1]
return buildUtil(In, post, 0, n - 1, pIndex)
# Function to find index of value in
# arr[start...end]. The function assumes
# that value is postsent in in[]
def search(arr, strt, end, value):
i = 0
for i in range(strt, end + 1):
if (arr[i] == value):
break
return i
# This function is here just to test
def preOrder(node):
if node == None:
return
print(node.data,end=" ")
preOrder(node.left)
preOrder(node.right)
# Driver code
if __name__ == '__main__':
In = [4, 8, 2, 5, 1, 6, 3, 7]
post = [8, 4, 5, 2, 6, 7, 3, 1]
n = len(In)
root = buildTree(In, post, n)
print("Preorder of the constructed tree :")
preOrder(root)
# This code is contributed by PranchalK
C#
// C# program to construct a tree using
// inorder and postorder traversals
using System;
/* A binary tree node has data, pointer
to left child and a pointer to right child */
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// Class Index created to implement
// pass by reference of Index
public class Index
{
public int index;
}
class GFG
{
/* Recursive function to construct binary
of size n from Inorder traversal in[] and
Postorder traversal post[]. Initial values
of inStrt and inEnd should be 0 and n -1.
The function doesn't do any error checking
for cases where inorder and postorder do
not form a tree */
public virtual Node buildUtil(int[] @in, int[] post,
int inStrt, int inEnd,
Index pIndex)
{
// Base case
if (inStrt > inEnd)
{
return null;
}
/* Pick current node from Postorder traversal
using postIndex and decrement postIndex */
Node node = new Node(post[pIndex.index]);
(pIndex.index)--;
/* If this node has no children
then return */
if (inStrt == inEnd)
{
return node;
}
/* Else find the index of this node
in Inorder traversal */
int iIndex = search(@in, inStrt, inEnd, node.data);
/* Using index in Inorder traversal,
construct left and right subtress */
node.right = buildUtil(@in, post, iIndex + 1,
inEnd, pIndex);
node.left = buildUtil(@in, post, inStrt,
iIndex - 1, pIndex);
return node;
}
// This function mainly initializes
// index of root and calls buildUtil()
public virtual Node buildTree(int[] @in,
int[] post, int n)
{
Index pIndex = new Index();
pIndex.index = n - 1;
return buildUtil(@in, post, 0, n - 1, pIndex);
}
/* Function to find index of value in
arr[start...end]. The function assumes
that value is postsent in in[] */
public virtual int search(int[] arr, int strt,
int end, int value)
{
int i;
for (i = strt; i <= end; i++)
{
if (arr[i] == value)
{
break;
}
}
return i;
}
/* This function is here just to test */
public virtual void preOrder(Node node)
{
if (node == null)
{
return;
}
Console.Write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
int[] @in = new int[] {4, 8, 2, 5, 1, 6, 3, 7};
int[] post = new int[] {8, 4, 5, 2, 6, 7, 3, 1};
int n = @in.Length;
Node root = tree.buildTree(@in, post, n);
Console.WriteLine("Preorder of the constructed tree : ");
tree.preOrder(root);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to construct a tree using inorder
// and postorder traversals
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class Node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
function buildUtil(In, post, inStrt, inEnd, postStrt, postEnd)
{
// Base case
if (inStrt > inEnd)
return null;
/* Pick current node from Postorder traversal using
postIndex and decrement postIndex */
let node = new Node(post[postEnd]);
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
let iIndex = search(In, inStrt, inEnd, node.data);
/* Using index in Inorder traversal, construct left
and right subtress */
node.left = buildUtil(
In, post, inStrt, iIndex - 1, postStrt,
postStrt - inStrt + iIndex - 1);
node.right = buildUtil(In, post, iIndex + 1, inEnd,
postEnd - inEnd + iIndex,
postEnd - 1);
return node;
}
/* Function to find index of value in arr[start...end]
The function assumes that value is postsent in in[]
*/
function search(arr,strt,end,value)
{
let i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
break;
}
return i;
}
/* This function is here just to test */
function preOrder(node)
{
if (node == null)
return;
document.write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver Code
let In=[4, 8, 2, 5, 1, 6, 3, 7];
let post=[8, 4, 5, 2, 6, 7, 3, 1];
let n = In.length;
let root
= buildUtil(In, post, 0, n - 1, 0, n - 1);
document.write(
"Preorder of the constructed tree : <br>");
preOrder(root);
// This code is contributed by unknown2108
</script>
Producción
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
Complejidad de tiempo: O(n 2 ), donde n es la longitud de la array dada en orden
Espacio auxiliar: O(n), para pila de llamadas recursivas
Enfoque optimizado: Podemos optimizar la solución anterior usando hash (unordered_map en C++ o HashMap en Java). Almacenamos índices de recorrido en orden en una tabla hash. Entonces esa búsqueda se puede hacer O (1) vez si se da ese elemento en el árbol que no se repite.
C++
/* C++ program to construct tree using inorder and
postorder traversals */
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left
child and a pointer to right child */
struct Node {
int data;
Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int data);
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
Node* buildUtil(int in[], int post[], int inStrt,
int inEnd, int* pIndex, unordered_map<int, int>& mp)
{
// Base case
if (inStrt > inEnd)
return NULL;
/* Pick current node from Postorder traversal
using postIndex and decrement postIndex */
int curr = post[*pIndex];
Node* node = newNode(curr);
(*pIndex)--;
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
/* Else find the index of this node in Inorder
traversal */
int iIndex = mp[curr];
/* Using index in Inorder traversal, construct
left and right subtress */
node->right = buildUtil(in, post, iIndex + 1,
inEnd, pIndex, mp);
node->left = buildUtil(in, post, inStrt,
iIndex - 1, pIndex, mp);
return node;
}
// This function mainly creates an unordered_map, then
// calls buildTreeUtil()
struct Node* buildTree(int in[], int post[], int len)
{
// Store indexes of all items so that we
// we can quickly find later
unordered_map<int, int> mp;
for (int i = 0; i < len; i++)
mp[in[i]] = i;
int index = len - 1; // Index in postorder
return buildUtil(in, post, 0, len - 1,
&index, mp);
}
/* Helper function that allocates a new node */
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
/* This function is here just to test */
void preOrder(Node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
// Driver code
int main()
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = sizeof(in) / sizeof(in[0]);
Node* root = buildTree(in, post, n);
cout << "Preorder of the constructed tree : \n";
preOrder(root);
return 0;
}
Java
/* Java program to construct tree using inorder and
postorder traversals */
import java.util.*;
class GFG
{
/* A binary tree node has data, pointer to left
child and a pointer to right child */
static class Node
{
int data;
Node left, right;
};
// Utility function to create a new node
/* Helper function that allocates a new node */
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
static Node buildUtil(int in[], int post[],
int inStrt, int inEnd)
{
// Base case
if (inStrt > inEnd)
return null;
/* Pick current node from Postorder traversal
using postIndex and decrement postIndex */
int curr = post[index];
Node node = newNode(curr);
(index)--;
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
/* Else find the index of this node in Inorder
traversal */
int iIndex = mp.get(curr);
/* Using index in Inorder traversal, con
left and right subtress */
node.right = buildUtil(in, post, iIndex + 1,
inEnd);
node.left = buildUtil(in, post, inStrt,
iIndex - 1);
return node;
}
static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
static int index;
// This function mainly creates an unordered_map, then
// calls buildTreeUtil()
static Node buildTree(int in[], int post[], int len)
{
// Store indexes of all items so that we
// we can quickly find later
for (int i = 0; i < len; i++)
mp.put(in[i], i);
index = len - 1; // Index in postorder
return buildUtil(in, post, 0, len - 1 );
}
/* This function is here just to test */
static void preOrder(Node node)
{
if (node == null)
return;
System.out.printf("%d ", node.data);
preOrder(node.left);
preOrder(node.right);
}
// Driver code
public static void main(String[] args)
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = in.length;
Node root = buildTree(in, post, n);
System.out.print("Preorder of the constructed tree : \n");
preOrder(root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to construct tree using inorder
# and postorder traversals
# A binary tree node has data, pointer to left
# child and a pointer to right child
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Recursive function to construct binary of size n
# from Inorder traversal in[] and Postorder traversal
# post[]. Initial values of inStrt and inEnd should
# be 0 and n -1. The function doesn't do any error
# checking for cases where inorder and postorder
# do not form a tree
def buildUtil(inn, post, innStrt, innEnd):
global mp, index
# Base case
if (innStrt > innEnd):
return None
# Pick current node from Postorder traversal
# using postIndex and decrement postIndex
curr = post[index]
node = Node(curr)
index -= 1
# If this node has no children then return
if (innStrt == innEnd):
return node
# Else find the index of this node inn
# Inorder traversal
iIndex = mp[curr]
# Using index inn Inorder traversal,
# construct left and right subtress
node.right = buildUtil(inn, post,
iIndex + 1, innEnd)
node.left = buildUtil(inn, post, innStrt,
iIndex - 1)
return node
# This function mainly creates an unordered_map,
# then calls buildTreeUtil()
def buildTree(inn, post, lenn):
global index
# Store indexes of all items so that we
# we can quickly find later
for i in range(lenn):
mp[inn[i]] = i
# Index in postorder
index = lenn - 1
return buildUtil(inn, post, 0, lenn - 1)
# This function is here just to test
def preOrder(node):
if (node == None):
return
print(node.data, end = " ")
preOrder(node.left)
preOrder(node.right)
# Driver Code
if __name__ == '__main__':
inn = [ 4, 8, 2, 5, 1, 6, 3, 7 ]
post = [ 8, 4, 5, 2, 6, 7, 3, 1 ]
n = len(inn)
mp, index = {}, 0
root = buildTree(inn, post, n)
print("Preorder of the constructed tree :")
preOrder(root)
# This code is contributed by mohit kumar 29
C#
/* C# program to construct tree using inorder and
postorder traversals */
using System;
using System.Collections.Generic;
class GFG
{
/* A binary tree node has data, pointer to left
child and a pointer to right child */
public
class Node
{
public
int data;
public
Node left, right;
};
// Utility function to create a new node
/* Helper function that allocates a new node */
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
static Node buildUtil(int []init, int []post,
int inStrt, int inEnd)
{
// Base case
if (inStrt > inEnd)
return null;
/* Pick current node from Postorder traversal
using postIndex and decrement postIndex */
int curr = post[index];
Node node = newNode(curr);
(index)--;
/* If this node has no children then return */
if (inStrt == inEnd)
return node;
/* Else find the index of this node in Inorder
traversal */
int iIndex = mp[curr];
/* Using index in Inorder traversal, con
left and right subtress */
node.right = buildUtil(init, post, iIndex + 1,
inEnd);
node.left = buildUtil(init, post, inStrt,
iIndex - 1);
return node;
}
static Dictionary<int,int> mp = new Dictionary<int,int>();
static int index;
// This function mainly creates an unordered_map, then
// calls buildTreeUtil()
static Node buildTree(int []init, int []post, int len)
{
// Store indexes of all items so that we
// we can quickly find later
for (int i = 0; i < len; i++)
mp.Add(init[i], i);
index = len - 1; // Index in postorder
return buildUtil(init, post, 0, len - 1 );
}
/* This function is here just to test */
static void preOrder(Node node)
{
if (node == null)
return;
Console.Write( node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver code
public static void Main(String[] args)
{
int []init = { 4, 8, 2, 5, 1, 6, 3, 7 };
int []post = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = init.Length;
Node root = buildTree(init, post, n);
Console.Write("Preorder of the constructed tree : \n");
preOrder(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/* JavaScript program to construct tree using inorder and
postorder traversals */
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
// Utility function to create a new node
/* Helper function that allocates a new node */
function newNode(data) {
var node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
function buildUtil(init, post, inStrt, inEnd) {
// Base case
if (inStrt > inEnd) {
return null;
}
/* Pick current node from Postorder traversal
using postIndex and decrement postIndex */
var curr = post[index];
var node = newNode(curr);
index--;
/* If this node has no children then return */
if (inStrt == inEnd) {
return node;
}
/* Else find the index of this node in Inorder
traversal */
var iIndex = mp[curr];
/* Using index in Inorder traversal, con
left and right subtress */
node.right = buildUtil(init, post, iIndex + 1, inEnd);
node.left = buildUtil(init, post, inStrt, iIndex - 1);
return node;
}
var mp = {};
var index;
// This function mainly creates an unordered_map, then
// calls buildTreeUtil()
function buildTree(init, post, len) {
// Store indexes of all items so that we
// we can quickly find later
for (var i = 0; i < len; i++) {
mp[init[i]] = i;
}
index = len - 1; // Index in postorder
return buildUtil(init, post, 0, len - 1);
}
/* This function is here just to test */
function preOrder(node) {
if (node == null) {
return;
}
document.write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver code
var init = [4, 8, 2, 5, 1, 6, 3, 7];
var post = [8, 4, 5, 2, 6, 7, 3, 1];
var n = init.length;
var root = buildTree(init, post, n);
document.write("Preorder of the constructed tree : <br>");
preOrder(root);
</script>
Producción
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n), el espacio adicional se usa debido a la pila de llamadas recursivas y para almacenar los elementos en el mapa.
Otro enfoque :
use stack y set sin usar recursividad.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer
to left child and a pointer to right
child */
struct Node
{
int data;
Node *left, *right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
/*Tree building function*/
Node *buildTree(int in[], int post[], int n)
{
// Create Stack of type Node*
stack<Node*> st;
// Create Set of type Node*
set<Node*> s;
// Initialise postIndex with n - 1
int postIndex = n - 1;
// Initialise root with NULL
Node* root = NULL;
for (int p = n - 1, i = n - 1; p>=0;)
{
// Initialise node with NULL
Node* node = NULL;
// Run do-while loop
do
{
// Initialise node with
// new Node(post[p]);
node = new Node(post[p]);
// Check is root is
// equal to NULL
if (root == NULL)
{
root = node;
}
// If size of set
// is greater than 0
if (st.size() > 0)
{
// If st.top() is present in the
// set s
if (s.find(st.top()) != s.end())
{
s.erase(st.top());
st.top()->left = node;
st.pop();
}
else
{
st.top()->right = node;
}
}
st.push(node);
} while (post[p--] != in[i] && p >=0);
node = NULL;
// If the stack is not empty and
// st.top()->data is equal to in[i]
while (st.size() > 0 && i>=0 &&
st.top()->data == in[i])
{
node = st.top();
// Pop elements from stack
st.pop();
i--;
}
// if node not equal to NULL
if (node != NULL)
{
s.insert(node);
st.push(node);
}
}
// Return root
return root;
}
/* for print preOrder Traversal */
void preOrder(Node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
// Driver Code
int main()
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = sizeof(in) / sizeof(in[0]);
// Function Call
Node* root = buildTree(in, post, n);
cout << "Preorder of the constructed tree : \n";
// Function Call for preOrder
preOrder(root);
return 0;
}
Java
// Java program for above approach
import java.io.*;
import java.util.*;
class GFG {
// Node class
static class Node {
int data;
Node left, right;
// Constructor
Node(int x)
{
data = x;
left = right = null;
}
}
// Tree building function
static Node buildTree(int in[], int post[], int n)
{
// Create Stack of type Node*
Stack<Node> st = new Stack<>();
// Create HashSet of type Node*
HashSet<Node> s = new HashSet<>();
// Initialise postIndex with n - 1
int postIndex = n - 1;
// Initialise root with null
Node root = null;
for (int p = n - 1, i = n - 1; p >= 0; ) {
// Initialise node with NULL
Node node = null;
// Run do-while loop
do {
// Initialise node with
// new Node(post[p]);
node = new Node(post[p]);
// Check is root is
// equal to NULL
if (root == null) {
root = node;
}
// If size of set
// is greater than 0
if (st.size() > 0) {
// If st.peek() is present in the
// set s
if (s.contains(st.peek())) {
s.remove(st.peek());
st.peek().left = node;
st.pop();
}
else {
st.peek().right = node;
}
}
st.push(node);
} while (post[p--] != in[i] && p >= 0);
node = null;
// If the stack is not empty and
// st.top().data is equal to in[i]
while (st.size() > 0 && i >= 0
&& st.peek().data == in[i]) {
node = st.peek();
// Pop elements from stack
st.pop();
i--;
}
// If node not equal to NULL
if (node != null) {
s.add(node);
st.push(node);
}
}
// Return root
return root;
}
// For print preOrder Traversal
static void preOrder(Node node)
{
if (node == null)
return;
System.out.printf("%d ", node.data);
preOrder(node.left);
preOrder(node.right);
}
// Driver Code
public static void main(String[] args)
{
int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = in.length;
// Function Call
Node root = buildTree(in, post, n);
System.out.print(
"Preorder of the constructed tree : \n");
// Function Call for preOrder
preOrder(root);
}
}
// This code is contributed by sujitmeshram
Python3
# Python program for above approach
# A binary tree node has data, pointer
# to left child and a pointer to right
# child
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# Tree building function
def buildTree(inorder, post, n):
# Create Stack of type Node
st = []
# Create Set of type Node
set = []
# Initialise postIndex with n - 1
postIndex = n - 1
# Initialise root with NULL
root = None
p = n-1
i = n-1
while p >= 0:
# Initialise node with NULL
node = None
# Run loop
while True:
# initialize new node
node = Node(post[p])
# check if root is equal to null
if root == None:
root = node
# If size of set is greater than 0
if len(st) > 0:
# If st top is present in the set s
if st[-1] in set:
set.remove(st[-1])
st[-1].left = node
st.pop()
else:
st[-1].right = node
st.append(node)
p -= 1
if post[p+1] == inorder[i] or p < 0:
break
node = None
# If the stack is not empty and st top data is equal to in[i]
while len(st) > 0 and i >= 0 and st[-1].data == inorder[i]:
node = st[-1]
# Pop elements from stack
st.pop()
i -= 1
# if node not equal to None
if node != None:
set.append(node)
st.append(node)
# Return root
return root
# for print preOrder Traversal
def preOrder(node):
if node == None:
return
print(node.data, end=" ")
preOrder(node.left)
preOrder(node.right)
# Driver Code
if __name__ == '__main__':
inorder = [4, 8, 2, 5, 1, 6, 3, 7]
post = [8, 4, 5, 2, 6, 7, 3, 1]
n = len(inorder)
# Function Call
root = buildTree(inorder, post, n)
print("Preorder of the constructed tree :")
# Function Call for preOrder
preOrder(root)
# This code is contribtued by Tapesh(tapeshdua420)
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG
{
// Node class
public
class Node
{
public
int data;
public
Node left, right;
// Constructor
public
Node(int x)
{
data = x;
left = right = null;
}
}
// Tree building function
static Node buildTree(int []init, int []post,
int n)
{
// Create Stack of type Node*
Stack<Node> st = new Stack<Node>();
// Create HashSet of type Node*
HashSet<Node> s = new HashSet<Node>();
// Initialise root with null
Node root = null;
for(int p = n - 1, i = n - 1; p >= 0;)
{
// Initialise node with NULL
Node node = null;
// Run do-while loop
do
{
// Initialise node with
// new Node(post[p]);
node = new Node(post[p]);
// Check is root is
// equal to NULL
if (root == null)
{
root = node;
}
// If size of set
// is greater than 0
if (st.Count > 0)
{
// If st.Peek() is present in the
// set s
if (s.Contains(st.Peek()))
{
s.Remove(st.Peek());
st.Peek().left = node;
st.Pop();
}
else
{
st.Peek().right = node;
}
}
st.Push(node);
}while (post[p--] != init[i] && p >= 0);
node = null;
// If the stack is not empty and
// st.top().data is equal to in[i]
while (st.Count > 0 && i >= 0 &&
st.Peek().data == init[i])
{
node = st.Peek();
// Pop elements from stack
st.Pop();
i--;
}
// If node not equal to NULL
if (node != null)
{
s.Add(node);
st.Push(node);
}
}
// Return root
return root;
}
// For print preOrder Traversal
static void preOrder(Node node)
{
if (node == null)
return;
Console.Write(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// Driver Code
public static void Main(String[] args)
{
int []init = { 4, 8, 2, 5, 1, 6, 3, 7 };
int []post = { 8, 4, 5, 2, 6, 7, 3, 1 };
int n = init.Length;
// Function Call
Node root = buildTree(init, post, n);
Console.Write(
"Preorder of the constructed tree : \n");
// Function Call for preOrder
preOrder(root);
}
}
// This code is contributed by aashish1995
Producción
Preorder of the constructed tree : 1 2 4 8 5 3 6 7
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n), El espacio adicional se utiliza para almacenar los elementos en la pila y establecer.
Este artículo es una contribución de Rishi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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