Dados los recorridos Preorder , Inorder y Postorder de algún árbol. Escriba un programa para verificar si todos son del mismo árbol.
Ejemplos:
Input : Inorder -> 4 2 5 1 3
Preorder -> 1 2 4 5 3
Postorder -> 4 5 2 3 1
Output : Yes
Explanation : All of the above three traversals are of
the same tree 1
/ \
2 3
/ \
4 5
Input : Inorder -> 4 2 5 1 3
Preorder -> 1 5 4 2 3
Postorder -> 4 1 2 3 5
Output : No
El enfoque más básico para resolver este problema será construir primero un árbol usando dos de los tres recorridos dados y luego hacer el tercer recorrido en este árbol construido y compararlo con el recorrido dado. Si ambos recorridos son iguales, imprima Sí; de lo contrario, imprima No. Aquí, usamos recorridos En orden y Preorden para construir el árbol. También podemos usar el recorrido Inorder y Postorder en lugar del recorrido Preorder para la construcción del árbol. Puede consultar esta publicación sobre cómo construir un árbol a partir de un recorrido dado en orden y en orden previo. Después de construir el árbol, obtendremos el recorrido Postorden de este árbol y lo compararemos con el recorrido Postorden dado.
A continuación se muestra la implementación del enfoque anterior:
C++
/* C++ program to check if all three given
traversals are of the same tree */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(int arr[], int strt, int end, int value)
{
for (int i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* Recursive function to construct binary tree
of size len from Inorder traversal in[] and
Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1.
The function doesn't do any error checking for
cases where inorder and preorder do not form a
tree */
Node* buildTree(int in[], int pre[], int inStrt,
int inEnd)
{
static int preIndex = 0;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal
using preIndex and increment preIndex */
Node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in
Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal,
construct left and right subtress */
tNode->left = buildTree(in, pre, inStrt, inIndex-1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* function to compare Postorder traversal
on constructed tree and given Postorder */
int checkPostorder(Node* node, int postOrder[], int index)
{
if (node == NULL)
return index;
/* first recur on left child */
index = checkPostorder(node->left,postOrder,index);
/* now recur on right child */
index = checkPostorder(node->right,postOrder,index);
/* Compare if data at current index in
both Postorder traversals are same */
if (node->data == postOrder[index])
index++;
else
return -1;
return index;
}
// Driver program to test above functions
int main()
{
int inOrder[] = {4, 2, 5, 1, 3};
int preOrder[] = {1, 2, 4, 5, 3};
int postOrder[] = {4, 5, 2, 3, 1};
int len = sizeof(inOrder)/sizeof(inOrder[0]);
// build tree from given
// Inorder and Preorder traversals
Node *root = buildTree(inOrder, preOrder, 0, len - 1);
// compare postorder traversal on constructed
// tree with given Postorder traversal
int index = checkPostorder(root,postOrder,0);
// If both postorder traversals are same
if (index == len)
cout << "Yes";
else
cout << "No";
return 0;
}
Java
/* Java program to check if all three given
traversals are of the same tree */
import java.util.*;
class GfG {
static int preIndex = 0;
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
static int search(int arr[], int strt, int end, int value)
{
for (int i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
return -1;
}
/* Recursive function to construct binary tree
of size len from Inorder traversal in[] and
Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1.
The function doesn't do any error checking for
cases where inorder and preorder do not form a
tree */
static Node buildTree(int in[], int pre[], int inStrt, int inEnd)
{
if(inStrt > inEnd)
return null;
/* Pick current node from Preorder traversal
using preIndex and increment preIndex */
Node tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in
Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode.data);
/* Using index in Inorder traversal,
construct left and right subtress */
tNode.left = buildTree(in, pre, inStrt, inIndex-1);
tNode.right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* function to compare Postorder traversal
on constructed tree and given Postorder */
static int checkPostorder(Node node, int postOrder[], int index)
{
if (node == null)
return index;
/* first recur on left child */
index = checkPostorder(node.left,postOrder,index);
/* now recur on right child */
index = checkPostorder(node.right,postOrder,index);
/* Compare if data at current index in
both Postorder traversals are same */
if (node.data == postOrder[index])
index++;
else
return -1;
return index;
}
// Driver program to test above functions
public static void main(String[] args)
{
int inOrder[] = {4, 2, 5, 1, 3};
int preOrder[] = {1, 2, 4, 5, 3};
int postOrder[] = {4, 5, 2, 3, 1};
int len = inOrder.length;
// build tree from given
// Inorder and Preorder traversals
Node root = buildTree(inOrder, preOrder, 0, len - 1);
// compare postorder traversal on constructed
// tree with given Postorder traversal
int index = checkPostorder(root,postOrder,0);
// If both postorder traversals are same
if (index == len)
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to check if
# all three given traversals
# are of the same tree
class node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
preIndex = 0
# Function to find index of value
# in arr[start...end]. The function
# assumes that value is present in in
def search(arr, strt, end, value):
for i in range(strt, end + 1):
if(arr[i] == value):
return i
# Recursive function to construct
# binary tree of size lenn from
# Inorder traversal in and Preorder
# traversal pre[]. Initial values
# of inStrt and inEnd should be 0
# and lenn -1. The function doesn't
# do any error checking for cases
# where inorder and preorder do not
# form a tree
def buildTree(inn, pre, inStrt, inEnd):
global preIndex
if(inStrt > inEnd):
return None
# Pick current node from Preorder
# traversal using preIndex and
# increment preIndex
tNode = node(pre[preIndex])
preIndex += 1
# If this node has no children
# then return
if (inStrt == inEnd):
return tNode
# Else find the index of this
# node in Inorder traversal
inIndex = search(inn, inStrt,
inEnd, tNode.data)
# Using index in Inorder traversal,
# construct left and right subtress
tNode.left = buildTree(inn, pre, inStrt,
inIndex - 1)
tNode.right = buildTree(inn, pre,
inIndex + 1, inEnd)
return tNode
# function to compare Postorder traversal
# on constructed tree and given Postorder
def checkPostorder(node, postOrder, index):
if (node == None):
return index
# first recur on left child
index = checkPostorder(node.left,
postOrder,
index)
# now recur on right child
index = checkPostorder(node.right,
postOrder,
index)
# Compare if data at current index in
# both Postorder traversals are same
if (node.data == postOrder[index]):
index += 1
else:
return - 1
return index
# Driver code
if __name__ == '__main__':
inOrder = [4, 2, 5, 1, 3]
preOrder = [1, 2, 4, 5, 3]
postOrder = [4, 5, 2, 3, 1]
lenn = len(inOrder)
# build tree from given
# Inorder and Preorder traversals
root = buildTree(inOrder, preOrder,
0, lenn - 1)
# compare postorder traversal on
# constructed tree with given
# Postorder traversal
index = checkPostorder(root, postOrder, 0)
# If both postorder traversals are same
if (index == lenn):
print("Yes")
else:
print("No")
# This code is contributed by Mohit Kumar 29
C#
/* C# program to check if all three given
traversals are of the same tree */
using System;
public class GfG
{
static int preIndex = 0;
// A Binary Tree Node
class Node
{
public int data;
public Node left, right;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
/* Function to find index of
value in arr[start...end]
The function assumes that
value is present in in[] */
static int search(int []arr, int strt,
int end, int value)
{
for (int i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
return -1;
}
/* Recursive function to construct
binary tree of size len from Inorder
traversal in[] and Preorder traversal
pre[]. Initial values of inStrt and
inEnd should be 0 and len -1. The
function doesn't do any error checking for
cases where inorder and preorder do not form a
tree */
static Node buildTree(int []In, int []pre,
int inStrt, int inEnd)
{
if(inStrt > inEnd)
return null;
/* Pick current node from Preorder traversal
using preIndex and increment preIndex */
Node tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in
Inorder traversal */
int inIndex = search(In, inStrt, inEnd, tNode.data);
/* Using index in Inorder traversal,
construct left and right subtress */
tNode.left = buildTree(In, pre, inStrt, inIndex - 1);
tNode.right = buildTree(In, pre, inIndex + 1, inEnd);
return tNode;
}
/* function to compare Postorder traversal
on constructed tree and given Postorder */
static int checkPostorder(Node node, int []postOrder, int index)
{
if (node == null)
return index;
/* first recur on left child */
index = checkPostorder(node.left,postOrder,index);
/* now recur on right child */
index = checkPostorder(node.right,postOrder,index);
/* Compare if data at current index in
both Postorder traversals are same */
if (node.data == postOrder[index])
index++;
else
return -1;
return index;
}
// Driver code
public static void Main()
{
int []inOrder = {4, 2, 5, 1, 3};
int []preOrder = {1, 2, 4, 5, 3};
int []postOrder = {4, 5, 2, 3, 1};
int len = inOrder.Length;
// build tree from given
// Inorder and Preorder traversals
Node root = buildTree(inOrder, preOrder, 0, len - 1);
// compare postorder traversal on constructed
// tree with given Postorder traversal
int index = checkPostorder(root, postOrder, 0);
// If both postorder traversals are same
if (index == len)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
/* Javascript program to check if all three given
traversals are of the same tree */
let preIndex = 0;
// A Binary Tree Node
class Node
{
// Utility function to create a new tree node
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
function search(arr,strt,end,value)
{
for (let i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
return -1;
}
/* Recursive function to construct binary tree
of size len from Inorder traversal in[] and
Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1.
The function doesn't do any error checking for
cases where inorder and preorder do not form a
tree */
function buildTree(In,pre,inStrt,inEnd)
{
if(inStrt > inEnd)
return null;
/* Pick current node from Preorder traversal
using preIndex and increment preIndex */
let tNode = new Node(pre[preIndex++]);
/* If this node has no children then return */
if (inStrt == inEnd)
return tNode;
/* Else find the index of this node in
Inorder traversal */
let inIndex = search(In, inStrt, inEnd, tNode.data);
/* Using index in Inorder traversal,
construct left and right subtress */
tNode.left = buildTree(In, pre, inStrt, inIndex-1);
tNode.right = buildTree(In, pre, inIndex+1, inEnd);
return tNode;
}
/* function to compare Postorder traversal
on constructed tree and given Postorder */
function checkPostorder(node,postOrder,index)
{
if (node == null)
return index;
/* first recur on left child */
index = checkPostorder(node.left,postOrder,index);
/* now recur on right child */
index = checkPostorder(node.right,postOrder,index);
/* Compare if data at current index in
both Postorder traversals are same */
if (node.data == postOrder[index])
index++;
else
return -1;
return index;
}
// Driver program to test above functions
let inOrder=[4, 2, 5, 1, 3];
let preOrder=[1, 2, 4, 5, 3];
let postOrder=[4, 5, 2, 3, 1];
let len = inOrder.length;
// build tree from given
// Inorder and Preorder traversals
let root = buildTree(inOrder, preOrder, 0, len - 1);
// compare postorder traversal on constructed
// tree with given Postorder traversal
let index = checkPostorder(root,postOrder,0);
// If both postorder traversals are same
if (index == len)
document.write("Yes");
else
document.write("No");
// This code is contributed by patel2127
</script>
Producción
Yes
Complejidad de tiempo : O (n * n ), donde n es el número de Nodes en el árbol.
Complejidad espacial: O(n) , para pila de llamadas
Este artículo es una contribución de Harsh Agarwal . 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.
Algoritmo eficiente que utiliza un mapa hash para almacenar índices de elementos en orden:
Mientras construimos el árbol a partir del recorrido Inorder y Preorder, debemos verificar si los recorridos Inorder y Preorder son válidos en sí mismos para algún árbol, y si es así, entonces siga construyendo el árbol, pero si el árbol binario válido no se puede construir a partir de inorder y preorder dados transversal, entonces debemos dejar de construir el árbol y devolver falso. Y también podemos construir el árbol desde el recorrido en orden y en orden previo en tiempo O (n) usando hashmap para almacenar los índices de la array de elementos en orden.
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
Node* buildTreeFromInorderPreorder(
int inStart, int inEnd, int& preIndex, int preorder[],
unordered_map<int, int>& inorderIndexMap,
bool& notPossible)
{
if (inStart > inEnd)
return NULL;
// build the current Node
int rootData = preorder[preIndex];
Node* root = new Node(rootData);
preIndex++;
// find the node in inorderIndexMap
if (inorderIndexMap.find(rootData)
== inorderIndexMap.end()) {
notPossible = true;
return root;
}
int inorderIndex = inorderIndexMap[rootData];
if (!(inStart <= inorderIndex
&& inorderIndex <= inEnd)) {
notPossible = true;
return root;
}
int leftInorderStart = inStart,
leftInorderEnd = inorderIndex - 1,
rightInorderStart = inorderIndex + 1,
rightInorderEnd = inEnd;
root->left = buildTreeFromInorderPreorder(
leftInorderStart, leftInorderEnd, preIndex,
preorder, inorderIndexMap, notPossible);
if (notPossible)
return root;
root->right = buildTreeFromInorderPreorder(
rightInorderStart, rightInorderEnd, preIndex,
preorder, inorderIndexMap, notPossible);
return root;
}
bool checkPostorderCorrect(Node* root, int& postIndex,
int postorder[])
{
if (!root)
return true;
if (!checkPostorderCorrect(root->left, postIndex,
postorder))
return false;
if (!checkPostorderCorrect(root->right, postIndex,
postorder))
return false;
return (root->data == postorder[postIndex++]);
}
void printPostorder(Node* root)
{
if (!root)
return;
printPostorder(root->left);
printPostorder(root->right);
cout << root->data << ", ";
}
void printInorder(Node* root)
{
if (!root)
return;
printInorder(root->left);
cout << root->data << ", ";
printInorder(root->right);
}
bool checktree(int preorder[], int inorder[],
int postorder[], int N)
{
// Your code goes here
if (N == 0)
return true;
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < N; i++)
inorderIndexMap[inorder[i]] = i;
int preIndex = 0;
// return checkInorderPreorder(0, N - 1, preIndex,
// preorder, inorderIndexMap) &&
// checkInorderPostorder(0, N - 1, postIndex, postorder,
// inorderIndexMap);
bool notPossible = false;
Node* root = buildTreeFromInorderPreorder(
0, N - 1, preIndex, preorder, inorderIndexMap,
notPossible);
if (notPossible)
return false;
int postIndex = 0;
return checkPostorderCorrect(root, postIndex,
postorder);
}
// Driver program to test above functions
int main()
{
int inOrder[] = { 4, 2, 5, 1, 3 };
int preOrder[] = { 1, 2, 4, 5, 3 };
int postOrder[] = { 4, 5, 2, 3, 1 };
int len = sizeof(inOrder) / sizeof(inOrder[0]);
// If both postorder traversals are same
if (checktree(preOrder, inOrder, postOrder, len))
cout << "Yes";
else
cout << "No";
return 0;
}
Producción
Yes
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(N), donde N es el número de Nodes en el árbol.
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