Use un recorrido de árbol en orden para determinar si un BST o un montón

Question

Dadas estas listas de travess de orden:

1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Necesito determinar si cada una de esas listas representan un montón de BST / min o MAX válido, o ninguno.
Estaba tratando de imaginar cómo abordar esto, pero además de forzar bruta todas las opciones posibles, no pude calcular una forma "inteligente" de resolver esto.

¿Qué indicadores puedo usar, si hay alguna, o la forma de resolver esto sería literalmente brutal forzando cada opción?

Answer 1

Ninguno de ellos puede ser un BST.Un recorrido en orden de un BST visite los vértices en orden no decreciente de sus claves (esto es fácil de probar por inducción).

Para determinar si son montones, observe que por el número de elementos en la lista, ya conoce la topología del árbol (montones son árboles completamente binarios hasta el nivel uno a último, y todas las hojas en elÚltimo nivel se embalan en el lado izquierdo).Luego, el ejercicio se reduce a la escritura de las claves dadas en el mismo orden del recorrido y la verificación si la propiedad del montón sostiene.

En el ejemplo específico, la primera secuencia no puede ser un recorrido de un montón desde que el árbol resultante tendría un camino con las teclas $ 23, 1, 53 $ (en el creciente orden de profundidad). El mismo argumento se aplica a la segunda secuencia para una ruta con las teclas $ 71, 32, 49 $ .