Проверить, принадлежат ли заданные обходы Preorder, Inorder и Postorder к одному дереву | Комплект 2

Опубликовано: 13 Января, 2022

Заданы обходы Preorder, Inorder и Postorder некоторого дерева. Задача - проверить, все ли они принадлежат к одному дереву.
Примеры:

 Ввод: Inorder -> 4 2 5 1 3
        Предзаказ -> 1 2 4 5 3
        Отправитель -> 4 5 2 3 1
Выход: Да
Exaplanation : Все три вышеупомянутых обхода 
такое же дерево. 1
                         / 
                        2 3
                      / 
                     4 5

Ввод: Inorder -> 4 2 5 1 3
        Предзаказ -> 1 5 4 2 3
        Отправитель -> 4 1 2 3 5
Выход: Нет
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Мы уже обсуждали подход к решению указанной выше проблемы путем построения дерева с использованием любых двух обходов в предыдущей статье.
В этой статье обсуждается подход без использования лишнего места.
Подход :

  1. Найдите первый элемент массива предварительного заказа в массиве inorder и сохраните его индекс как idx, если он не существует, верните False. Кроме того, проверьте, присутствует ли этот элемент в массиве postorder или нет. Если это не так, верните False.
  2. Все, начиная с 0-го индекса для inorder и postorder и с 1-го индекса для preorder длины idx, становится левым поддеревом для первого элемента массива preorder.
  3. Все, начиная с позиции idx + 1 для inorder и preorder и из idx для postorder длины ( length-idx-1 ), становится правым поддеревом для первого элемента массива preorder.
  4. Повторяйте шаги с 1 по 3 рекурсивно, пока длина массивов не станет равной 0 (в этом случае мы
    return true) или 1 (в этом случае мы возвращаем True, только если все три массива равны, иначе False).

Below is the implementation of the above approach: 

C++

// C++ program to check if the given
// three traversals are of the same
// tree or not
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if traversals are
// of the same tree
int checktree(int preorder[], int inorder[],
              int postorder[], int len)
{
 
    // if the array lengths are 0,
    // then all of them are obviously equal
    if (len == 0)
        return 1;
 
    // if array lengths are 1,
    // then check if all of them are equal
    if (len == 1)
        return (preorder[0] == inorder[0])
               && (inorder[0] == postorder[0]);
 
    // search for first element of preorder
    // in inorder array
    int idx = -1, f = 0;
    for (int i = 0; i < len; ++i)
        if (inorder[i] == preorder[0]) {
            idx = i;
            break;
        }
   
    if(idx != -1){
      for(int i = 0; i < len; i++)
        if(preorder[0] == postorder[i]){f = 1; break;}
    }
 
    if (idx == -1 || f == 0)
        return 0;
 
    // check for the left subtree
    int ret1
        = checktree(preorder + 1, inorder, postorder, idx);
 
    // check for the right subtree
    int ret2
        = checktree(preorder + idx + 1, inorder + idx + 1,
                    postorder + idx, len - idx - 1);
 
    // return 1 only if both of them are
    // correct else 0
    return (ret1 && ret2);
}
 
// Driver Code
int main()
{
    // Traversal Arrays
    int inorder[] = { 4, 2, 5, 1, 3 };
    int preorder[] = { 1, 2, 4, 5, 3 };
    int postorder[] = { 4, 5, 2, 3, 1 };
    int len1 = sizeof(inorder) / sizeof(inorder[0]);
    int len2 = sizeof(preorder) / sizeof(preorder[0]);
    int len3 = sizeof(postorder) / sizeof(postorder[0]);
 
    // Check if all the array lengths are equal
    if ((len1 == len2) && (len2 == len3)) {
 
        bool res
            = checktree(preorder, inorder, postorder, len1);
 
        (res) ? cout << "Yes" : cout << "No";
    }
    else
        cout << "No ";
 
    return 0;
}

Java

// Java program to check if the given
// three traversals are of the same
// tree or not
class GFG {
 
    // Function to check if traversals are
    // of the same tree
    static boolean checktree(int preorder[], int s,
                             int inorder[], int s1,
                             int postorder[], int s2,
                             int len)
    {
 
        // if the array lengths are 0,
        // then all of them are obviously equal
        if (len == 0)
            return true;
 
        // if array lengths are 1,
        // then check if all of them are equal
        if (len == 1)
            return ((preorder[s] == inorder[s1])
                    && (inorder[s1] == postorder[s2]));
 
        // search for first element of preorder
        // in inorder array
        int idx = -1;
        for (int i = s1; i < s1 + len; ++i)
            if (inorder[i] == preorder[s]) {
                idx = i;
                break;
            }
 
        if (idx == -1)
            return false;
        idx = idx - s1;
 
        // check for the left subtree
        boolean ret1 = checktree(preorder, s + 1, inorder,
                                 s1, postorder, s2, idx);
 
        // check for the right subtree
        boolean ret2 = checktree(
            preorder, s + idx + 1, inorder, s1 + idx + 1,
            postorder, s2 + idx, len - idx - 1);
 
        // return 1 only if both of them are
        // correct else 0
        return (ret1 && ret2);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Traversal Arrays
        int inorder[] = { 4, 2, 5, 1, 3 };
        int preorder[] = { 1, 2, 4, 5, 3 };
        int postorder[] = { 4, 5, 2, 3, 1 };
        int len1 = inorder.length;
        int len2 = preorder.length;
        int len3 = postorder.length;
 
        // Check if all the array lengths are equal
        if ((len1 == len2) && (len2 == len3)) {
 
            boolean res = checktree(preorder, 0, inorder, 0,
                                    postorder, 0, len1);
 
            System.out.print(((res) ? "Yes" : "No"));
        }
        else
            System.out.print("No ");
    }
}
 
// This code is contributed by Arnab Kundu

Python

# Python program to check if the given
# three traversals are of the same
# tree or not
 
# Function to check if all three traversals
# are of the same tree
 
 
def checktree(preorder, inorder, postorder, length):
 
    # if the array lengths are 0,
    # then all of them are obviously equal
    if length == 0:
        return 1
 
    # if array lengths are 1,
    # then check if all of them are equal
    if length == 1:
        return (preorder[0] == inorder[0]) and
               (inorder[0] == postorder[0])
 
    # search for first element of preorder
    # in inorder array
    idx = -1
 
    for i in range(length):
        if inorder[i] == preorder[0]:
            idx = i
            break
 
    if idx == -1:
        return 0
 
    # check for the left subtree
    ret1 = checktree(preorder[1:], inorder, postorder, idx)
 
    # check for the right subtree
    ret2 = checktree(preorder[idx + 1:], inorder[idx + 1:],
                     postorder[idx:], length-idx-1)
 
    # return 1 only if both of them are correct else 0
    return (ret1 and ret2)
 
 
# Driver Code
if __name__ == "__main__":
    inorder = [4, 2, 5, 1, 3]
    preorder = [1, 2, 4, 5, 3]
    postorder = [4, 5, 2, 3, 1]
    len1 = len(inorder)
    len2 = len(preorder)
    len3 = len(postorder)
 
    # check if all the array lengths are equal
    if (len1 == len2) and (len2 == len3):
        correct = checktree(preorder, inorder,
                            postorder, len1)
        if (correct):
            print("Yes")
        else:
            print("No")
    else:
        print("No")

C#

// C# program to check if the given
// three traversals are of the same
// tree or not
using System;
 
class GFG {
 
    // Function to check if traversals are
    // of the same tree
    static bool checktree(int[] preorder, int s,
                          int[] inorder, int s1,
                          int[] postorder, int s2, int len)
    {
 
        // if the array lengths are 0,
        // then all of them are obviously equal
        if (len == 0)
            return true;
 
        // if array lengths are 1,
        // then check if all of them are equal
        if (len == 1)
            return ((preorder[s] == inorder[s1])
                    && (inorder[s1] == postorder[s2]));
 
        // search for first element of preorder
        // in inorder array
        int idx = -1;
        for (int i = s1; i < len; ++i)
            if (inorder[i] == preorder[s]) {
                idx = i;
                break;
            }
 
        if (idx == -1)
            return false;
 
        // check for the left subtree
        bool ret1 = checktree(preorder, s + 1, inorder, s1,
                              postorder, s2, idx);
 
        // check for the right subtree
        bool ret2 = checktree(
            preorder, s + idx + 1, inorder, s1 + idx + 1,
            postorder, s2 + idx, len - idx - 1);
 
        // return 1 only if both of them are
        // correct else 0
        return (ret1 && ret2);
    }
 
    // Driver Code
    static public void Main()
    {
        // Traversal Arrays
        int[] inorder = { 4, 2, 5, 1, 3 };
        int[] preorder = { 1, 2, 4, 5, 3 };
        int[] postorder = { 4, 5, 2, 3, 1 };
        int len1 = inorder.Length;
        int len2 = preorder.Length;
        int len3 = postorder.Length;
 
        // Check if all the array lengths are equal
        if ((len1 == len2) && (len2 == len3)) {
 
            bool res = checktree(preorder, 0, inorder, 0,
                                 postorder, 0, len1);
 
            Console.Write(((res) ? "Yes" : "No"));
        }
        else
            Console.Write("No ");
    }
}
 
// This code is contributed by ajit

PHP

<?php
// PHP program to check if the given
// three traversals are of the same
// tree or not
 
 
// Function to check if traversals are
// of the same tree
function checktree($preorder, $inorder,
                $postorder, $len)
{
 
    // if the array lengths are 0,
    // then all of them are obviously equal
    if ($len == 0)
        return 1;
 
    // if array lengths are 1,
    // then check if all of them are equal
    if ($len == 1)
        return ($preorder[0] == $inorder[0])
            && ($inorder[0] == $postorder[0]);
 
    // search for first element of preorder
    // in inorder array
    $idx = -1;
    for ($i = 0; $i < $len; ++$i)
        if ($inorder[$i] == $preorder[0])
        {
            $idx = $i;
            break;
        }
 
    if ($idx == -1)
        return 0;
 
    // check for the left subtree
    $ret1 = checktree(array_slice($preorder,1), $inorder,
                        $postorder, $idx);
 
    // check for the right subtree
    $ret2 = checktree(array_slice($preorder,$idx + 1),
                        array_slice
C

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Функция getchar в C
20 Февраля, 2023
Использование goto для обработки исключений в C
20 Февраля, 2023
Почему нельзя использовать константную переменную для определения начального размера массива в C?
20 Февраля, 2023
Программа C для отображения времени в другом формате страны
18 Февраля, 2023
Программа C для поиска чисел Армстронга от 1 до 1000
28 Января, 2023
Программа C для создания и печати базы данных студентов с использованием структуры
28 Января, 2023
Передача указателей на функции в C
28 Января, 2023
C – файловый ввод/вывод
28 Января, 2023