Use a árvore travessia de entrada para determinar se um BST ou HEAP

Question

Dado estas listas de travessias de encomendas:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

Eu preciso determinar se cada uma dessas listas representam uma pilha válida / min ou max ou nenhuma.
Eu estava tentando descobrir como abordar isso, mas além de forçar Brute todas as opções possíveis que não consegui descobrir uma maneira "inteligente" para resolver isso.

Quais indicadores posso usar, se houver alguma, ou a maneira de resolver isso seria literalmente bruta forçando todas as opções?

Answer 1

Nenhum deles pode ser um BST.Uma travessia em ordem de uma BST visita os vértices em ordem não decrescente de suas chaves (isso é fácil de provar por indução).

Para determinar se eles são montes, observe que pelo número de elementos na lista que você já conhece a topologia da árvore (os montes são completamente binário de árvores até o último nível, e todas as folhas noÚltimo nível são embalados no lado esquerdo).Em seguida, o exercício se resume a escrever as teclas dadas na mesma ordem da travessia e verificando se a propriedade Heap é válida.

No exemplo específico, a primeira sequência não pode ser uma travessia em ordem de uma pilha, já que a árvore resultante teria um caminho com chaves $ 23, 1, 53 $ (em ordem crescente de profundidade). O mesmo argumento aplica-se à segunda sequência para um caminho com chaves $ 71, 32, 49 $ .