Dadas dos arrays pre[] e in[] que representan el recorrido en orden previo y en orden del árbol binario , la tarea es verificar si los recorridos dados son válidos para cualquier árbol binario o no sin construir el árbol . Si es posible, imprima Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: pre[] = {1, 2, 4, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Salida: Sí
Explicación:
Ambos recorridos son válidos para el siguiente árbol binario:
1
/ \
2 3
/ \ /
4 5 6
\ \
7 8Entrada: pre[] = {1, 2, 69, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Salida: No
Enfoque: La idea es usar una técnica similar para construir el árbol binario a partir de recorridos en orden y en orden previo , excepto que no es para construir el árbol, sino para verificar si el recorrido en orden actual de ese árbol (subárbol) y el Índice de orden previo actual es válido o no en cada llamada recursiva o no.
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;
// C++ program to check if given inorder
// and preorder traversals of size N are
// valid for a binary tree or not
bool checkInorderPreorderUtil(
int inStart, int inEnd,
int& preIndex, int preorder[],
unordered_map<int, int>& inorderIndexMap)
{
if (inStart > inEnd)
return true;
// Build the current Node
int rootData = preorder[preIndex];
preIndex++;
// If the element at current Index
// is not present in the inorder
// then tree can't be built
if (inorderIndexMap.find(rootData)
== inorderIndexMap.end())
return false;
int inorderIndex = inorderIndexMap[rootData];
// If the inorderIndex does not fall
// within the range of the inorder
// traversal of the current tree
// then return false
if (!(inStart <= inorderIndex
&& inorderIndex <= inEnd))
return false;
int leftInorderStart = inStart;
int leftInorderEnd = inorderIndex - 1;
int rightInorderStart = inorderIndex + 1;
int rightInorderEnd = inEnd;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
if (!checkInorderPreorderUtil(
leftInorderStart, leftInorderEnd,
preIndex, preorder, inorderIndexMap))
return false;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
else
return checkInorderPreorderUtil(
rightInorderStart, rightInorderEnd,
preIndex, preorder, inorderIndexMap);
}
// Function to check for the validation of
// inorder and preorder
string checkInorderPreorder(
int pre[], int in[], int n)
{
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < n; i++)
inorderIndexMap[in[i]] = i;
int preIndex = 0;
if (checkInorderPreorderUtil(
0, n - 1, preIndex,
pre, inorderIndexMap)) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
int main()
{
int pre[] = { 1, 2, 4, 5, 7, 3, 6, 8 };
int in[] = { 4, 2, 5, 7, 1, 6, 8, 3 };
int N = sizeof(pre) / sizeof(pre[0]);
cout << checkInorderPreorder(pre, in, N);
return 0;
}
Java
// Java program to check if given inorder
// and preorder traversals of size N are
// valid for a binary tree or not
import java.util.*;
class GFG
{
static int preIndex;
static HashMap<Integer,Integer> inorderIndexMap = new HashMap<Integer,Integer>();
static boolean checkInorderPreorderUtil(
int inStart, int inEnd,
int preorder[])
{
if (inStart > inEnd)
return true;
// Build the current Node
int rootData = preorder[preIndex];
preIndex++;
// If the element at current Index
// is not present in the inorder
// then tree can't be built
if (!inorderIndexMap.containsKey(rootData))
return false;
int inorderIndex = inorderIndexMap.get(rootData);
// If the inorderIndex does not fall
// within the range of the inorder
// traversal of the current tree
// then return false
if (!(inStart <= inorderIndex
&& inorderIndex <= inEnd))
return false;
int leftInorderStart = inStart;
int leftInorderEnd = inorderIndex - 1;
int rightInorderStart = inorderIndex + 1;
int rightInorderEnd = inEnd;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
if (!checkInorderPreorderUtil(
leftInorderStart, leftInorderEnd,preorder))
return false;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
else
return checkInorderPreorderUtil(
rightInorderStart, rightInorderEnd,
preorder);
}
// Function to check for the validation of
// inorder and preorder
static String checkInorderPreorder(
int pre[], int in[], int n)
{
//HashMap<Integer,Integer> inorderIndexMap = new HashMap<Integer,Integer>();
for (int i = 0; i < n; i++)
inorderIndexMap.put(in[i], i);
preIndex = 0;
if (checkInorderPreorderUtil(
0, n - 1,
pre)) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
public static void main(String[] args)
{
int pre[] = { 1, 2, 4, 5, 7, 3, 6, 8 };
int in[] = { 4, 2, 5, 7, 1, 6, 8, 3 };
int N = pre.length;
System.out.print(checkInorderPreorder(pre, in, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to check if given inorder
# and preorder traversals of size N are
# valid for a binary tree or not
def checkInorderPreorderUtil(inStart, inEnd, preIndex, preorder, inorderIndexMap):
if (inStart > inEnd):
return True
# Build the current Node
rootData = preorder[preIndex]
preIndex += 1
# If the element at current Index
# is not present in the inorder
# then tree can't be built
if (rootData in inorderIndexMap):
return False
inorderIndex = inorderIndexMap[rootData]
# If the inorderIndex does not fall
# within the range of the inorder
# traversal of the current tree
# then return false
if ((inStart <= inorderIndex and inorderIndex <= inEnd)==False):
return False
leftInorderStart = inStart
leftInorderEnd = inorderIndex - 1
rightInorderStart = inorderIndex + 1
rightInorderEnd = inEnd
# Check if the left subtree can be
# built from the inorder traversal
# of the left subtree and preorder
if(checkInorderPreorderUtil(leftInorderStart,leftInorderEnd,preIndex,preorder,inorderIndexMap)==False):
return False
# Check if the left subtree can be
# built from the inorder traversal
# of the left subtree and preorder
else:
return checkInorderPreorderUtil(rightInorderStart, rightInorderEnd,preIndex, preorder, inorderIndexMap)
# Function to check for the validation of
# inorder and preorder
def checkInorderPreorder(pre, inv,n):
inorderIndexMap = {}
for i in range(n):
inorderIndexMap[inv[i]] = i
preIndex = 0
if (checkInorderPreorderUtil(0, n - 1, preIndex,pre, inorderIndexMap)):
return "No"
else:
return "Yes"
# Driver Code
if __name__ == '__main__':
pre = [1, 2, 4, 5, 7, 3, 6, 8]
inv = [4, 2, 5, 7, 1, 6, 8, 3]
N = len(pre)
print(checkInorderPreorder(pre, inv, N))
# This code is contributed by ipg2016107.
C#
// C# program to check if given inorder
// and preorder traversals of size N are
// valid for a binary tree or not
using System;
using System.Collections.Generic;
public class GFG
{
static int preIndex;
static Dictionary<int,int> inorderIndexMap = new Dictionary<int,int>();
static bool checkInorderPreorderUtil(
int inStart, int inEnd,
int []preorder)
{
if (inStart > inEnd)
return true;
// Build the current Node
int rootData = preorder[preIndex];
preIndex++;
// If the element at current Index
// is not present in the inorder
// then tree can't be built
if (!inorderIndexMap.ContainsKey(rootData))
return false;
int inorderIndex = inorderIndexMap[rootData];
// If the inorderIndex does not fall
// within the range of the inorder
// traversal of the current tree
// then return false
if (!(inStart <= inorderIndex
&& inorderIndex <= inEnd))
return false;
int leftInorderStart = inStart;
int leftInorderEnd = inorderIndex - 1;
int rightInorderStart = inorderIndex + 1;
int rightInorderEnd = inEnd;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
if (!checkInorderPreorderUtil(
leftInorderStart, leftInorderEnd,preorder))
return false;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
else
return checkInorderPreorderUtil(
rightInorderStart, rightInorderEnd,
preorder);
}
// Function to check for the validation of
// inorder and preorder
static String checkInorderPreorder(
int []pre, int []inn, int n)
{
// Dictionary<int,int> inorderIndexMap = new Dictionary<int,int>();
for (int i = 0; i < n; i++)
inorderIndexMap.Add(inn[i], i);
preIndex = 0;
if (checkInorderPreorderUtil(
0, n - 1,
pre)) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
public static void Main(String[] args)
{
int []pre = { 1, 2, 4, 5, 7, 3, 6, 8 };
int []inn = { 4, 2, 5, 7, 1, 6, 8, 3 };
int N = pre.Length;
Console.Write(checkInorderPreorder(pre, inn, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let inorderIndexMap = new Map();
let preIndex;
function checkInorderPreorderUtil( inStart, inEnd, preorder)
{
if (inStart > inEnd)
return true;
// Build the current Node
let rootData = preorder[preIndex];
preIndex++;
// If the element at current Index
// is not present in the inorder
// then tree can't be built
if (!inorderIndexMap.has(rootData))
return false;
let inorderIndex = inorderIndexMap.get(rootData);
// If the inorderIndex does not fall
// within the range of the inorder
// traversal of the current tree
// then return false
if (!(inStart <= inorderIndex
&& inorderIndex <= inEnd))
return false;
let leftInorderStart = inStart;
let leftInorderEnd = inorderIndex - 1;
let rightInorderStart = inorderIndex + 1;
let rightInorderEnd = inEnd;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
if (!checkInorderPreorderUtil(
leftInorderStart, leftInorderEnd, preorder))
return false;
// Check if the left subtree can be
// built from the inorder traversal
// of the left subtree and preorder
else
return checkInorderPreorderUtil(
rightInorderStart, rightInorderEnd, preorder);
}
// Function to check for the validation of
// inorder and preorder
function checkInorderPreorder(pre, inn, n)
{
for (let i = 0; i < n; i++)
inorderIndexMap.set(inn[i], i);
preIndex = 0;
if (checkInorderPreorderUtil(
0, n - 1,
pre )) {
return "Yes";
}
else {
return "No";
}
}
// Driver Code
let pre = [ 1, 2, 4, 5, 7, 3, 6, 8 ];
let inn = [ 4, 2, 5, 7, 1, 6, 8, 3 ];
let N = pre.length;
document.write(checkInorderPreorder(pre, inn, N));
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
Yes
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