Compruebe si los recorridos Preorder, Inorder y Postorder dados son del mismo árbol

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *