Dada una array que representa el recorrido previo al pedido de BST, imprima su recorrido posterior al pedido.
Ejemplos:
Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40
Requisito previo: construir BST a partir de un recorrido de preorden dado
Enfoque simple : una solución simple es construir primero BST a partir de un recorrido de preorden dado como se describe en esta publicación. Después de construir el árbol, realice un recorrido posorden en él.
Enfoque eficiente: Un enfoque eficiente es encontrar el recorrido posterior al orden sin construir el árbol. La idea es atravesar la array de preorden dada y mantener un rango en el que debe estar el elemento actual. Esto es para garantizar que la propiedad BST siempre se cumpla. Inicialmente, el rango se establece en {minval = INT_MIN, maxval = INT_MAX}. En el recorrido en preorden, el primer elemento siempre es la raíz y, sin duda, se encontrará en el rango inicial. Así que almacene el primer elemento de la array de pedidos anticipados. En el recorrido posterior al orden, primero se imprimen los subárboles izquierdo y derecho y luego se imprimen los datos raíz. Entonces, primero se realiza una llamada recursiva para los subárboles izquierdo y derecho y luego se imprime el valor de la raíz. Para el rango del subárbol izquierdo se actualiza a {minval, root->data} y para el rango del subárbol derecho se actualiza a {root->data, maxval}.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for finding postorder
// traversal of BST from preorder traversal
#include <bits/stdc++.h>
using namespace std;
// Function to find postorder traversal from
// preorder traversal.
void findPostOrderUtil(int pre[], int n, int minval,
int maxval, int& preIndex)
{
// If entire preorder array is traversed then
// return as no more element is left to be
// added to post order array.
if (preIndex == n)
return;
// If array element does not lie in range specified,
// then it is not part of current subtree.
if (pre[preIndex] < minval || pre[preIndex] > maxval) {
return;
}
// Store current value, to be printed later, after
// printing left and right subtrees. Increment
// preIndex to find left and right subtrees,
// and pass this updated value to recursive calls.
int val = pre[preIndex];
preIndex++;
// All elements with value between minval and val
// lie in left subtree.
findPostOrderUtil(pre, n, minval, val, preIndex);
// All elements with value between val and maxval
// lie in right subtree.
findPostOrderUtil(pre, n, val, maxval, preIndex);
cout << val << " ";
}
// Function to find postorder traversal.
void findPostOrder(int pre[], int n)
{
// To store index of element to be
// traversed next in preorder array.
// This is passed by reference to
// utility function.
int preIndex = 0;
findPostOrderUtil(pre, n, INT_MIN, INT_MAX, preIndex);
}
// Driver code
int main()
{
int pre[] = { 40, 30, 35, 80, 100 };
int n = sizeof(pre) / sizeof(pre[0]);
// Calling function
findPostOrder(pre, n);
return 0;
}
Java
// Java program for finding postorder
// traversal of BST from preorder traversal
import java.util.*;
class Solution {
static class INT {
int data;
INT(int d) { data = d; }
}
// Function to find postorder traversal from
// preorder traversal.
static void findPostOrderUtil(int pre[], int n,
int minval, int maxval,
INT preIndex)
{
// If entire preorder array is traversed then
// return as no more element is left to be
// added to post order array.
if (preIndex.data == n)
return;
// If array element does not lie in range specified,
// then it is not part of current subtree.
if (pre[preIndex.data] < minval
|| pre[preIndex.data] > maxval) {
return;
}
// Store current value, to be printed later, after
// printing left and right subtrees. Increment
// preIndex to find left and right subtrees,
// and pass this updated value to recursive calls.
int val = pre[preIndex.data];
preIndex.data++;
// All elements with value between minval and val
// lie in left subtree.
findPostOrderUtil(pre, n, minval, val, preIndex);
// All elements with value between val and maxval
// lie in right subtree.
findPostOrderUtil(pre, n, val, maxval, preIndex);
System.out.print(val + " ");
}
// Function to find postorder traversal.
static void findPostOrder(int pre[], int n)
{
// To store index of element to be
// traversed next in preorder array.
// This is passed by reference to
// utility function.
INT preIndex = new INT(0);
findPostOrderUtil(pre, n, Integer.MIN_VALUE,
Integer.MAX_VALUE, preIndex);
}
// Driver code
public static void main(String args[])
{
int pre[] = { 40, 30, 35, 80, 100 };
int n = pre.length;
// Calling function
findPostOrder(pre, n);
}
}
// This code is contributed
// by Arnab Kundu
Python3
"""Python3 program for finding postorder traversal of BST from preorder traversal""" INT_MIN = -2**31 INT_MAX = 2**31 # Function to find postorder traversal # from preorder traversal. def findPostOrderUtil(pre, n, minval, maxval, preIndex): # If entire preorder array is traversed # then return as no more element is left # to be added to post order array. if (preIndex[0] == n): return # If array element does not lie in # range specified, then it is not # part of current subtree. if (pre[preIndex[0]] < minval or pre[preIndex[0]] > maxval): return # Store current value, to be printed later, # after printing left and right subtrees. # Increment preIndex to find left and right # subtrees, and pass this updated value to # recursive calls. val = pre[preIndex[0]] preIndex[0] += 1 # All elements with value between minval # and val lie in left subtree. findPostOrderUtil(pre, n, minval, val, preIndex) # All elements with value between val # and maxval lie in right subtree. findPostOrderUtil(pre, n, val, maxval, preIndex) print(val, end=" ") # Function to find postorder traversal. def findPostOrder(pre, n): # To store index of element to be # traversed next in preorder array. # This is passed by reference to # utility function. preIndex = [0] findPostOrderUtil(pre, n, INT_MIN, INT_MAX, preIndex) # Driver Code if __name__ == '__main__': pre = [40, 30, 35, 80, 100] n = len(pre) # Calling function findPostOrder(pre, n) # This code is contributed by # SHUBHAMSINGH10
C#
// C# program for finding postorder
// traversal of BST from preorder traversal
using System;
class GFG {
public class INT {
public int data;
public INT(int d) { data = d; }
}
// Function to find postorder traversal from
// preorder traversal.
public static void findPostOrderUtil(int[] pre, int n,
int minval,
int maxval,
INT preIndex)
{
// If entire preorder array is traversed
// then return as no more element is left
// to be added to post order array.
if (preIndex.data == n) {
return;
}
// If array element does not lie in
// range specified, then it is not
// part of current subtree.
if (pre[preIndex.data] < minval
|| pre[preIndex.data] > maxval) {
return;
}
// Store current value, to be printed
// later, after printing left and right
// subtrees. Increment preIndex to find
// left and right subtrees, and pass this
// updated value to recursive calls.
int val = pre[preIndex.data];
preIndex.data++;
// All elements with value between
// minval and val lie in left subtree.
findPostOrderUtil(pre, n, minval, val, preIndex);
// All elements with value between
// val and maxval lie in right subtree.
findPostOrderUtil(pre, n, val, maxval, preIndex);
Console.Write(val + " ");
}
// Function to find postorder traversal.
public static void findPostOrder(int[] pre, int n)
{
// To store index of element to be
// traversed next in preorder array.
// This is passed by reference to
// utility function.
INT preIndex = new INT(0);
findPostOrderUtil(pre, n, int.MinValue,
int.MaxValue, preIndex);
}
// Driver code
public static void Main(string[] args)
{
int[] pre = new int[] { 40, 30, 35, 80, 100 };
int n = pre.Length;
// Calling function
findPostOrder(pre, n);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program for finding postorder
// traversal of BST from preorder traversal
class INT
{
constructor(d)
{
this.data=d;
}
}
// Function to find postorder traversal from
// preorder traversal.
function findPostOrderUtil(pre,n,minval,maxval,preIndex)
{
// If entire preorder array is traversed then
// return as no more element is left to be
// added to post order array.
if (preIndex.data == n)
return;
// If array element does not lie in range specified,
// then it is not part of current subtree.
if (pre[preIndex.data] < minval
|| pre[preIndex.data] > maxval) {
return;
}
// Store current value, to be printed later, after
// printing left and right subtrees. Increment
// preIndex to find left and right subtrees,
// and pass this updated value to recursive calls.
let val = pre[preIndex.data];
preIndex.data++;
// All elements with value between minval and val
// lie in left subtree.
findPostOrderUtil(pre, n, minval, val, preIndex);
// All elements with value between val and maxval
// lie in right subtree.
findPostOrderUtil(pre, n, val, maxval, preIndex);
document.write(val + " ");
}
// Function to find postorder traversal.
function findPostOrder(pre,n)
{
// To store index of element to be
// traversed next in preorder array.
// This is passed by reference to
// utility function.
let preIndex = new INT(0);
findPostOrderUtil(pre, n, Number.MIN_VALUE,
Number.MAX_VALUE, preIndex);
}
// Driver code
let pre=[40, 30, 35, 80, 100];
let n = pre.length;
// Calling function
findPostOrder(pre, n);
// This code is contributed by unknown2108
</script>
Producción
35 30 100 80 40
Complejidad temporal: O(N), donde N es el número de Nodes.
Espacio auxiliar: O (N) (tamaño de la pila de llamadas de función)