Início / coding / Perguntas / 79569247
Accepted
Linda
Asked: 2025-04-11 23:44:13 +0800 CST

É possível reconstruir uma árvore binária a partir de sua travessia de pós-ordem e pré-ordem?

  • 772

Entendo que podemos reconstruir uma árvore binária a partir de sua travessia em ordem E (pós-ordem OU pré-ordem).

No entanto, eu me pergunto se reconstruí-lo a partir de sua travessia de pós-ordem E pré-ordem também é possível?

algorithm

1 respostas

  1. Best Answer

    A resposta curta é NÃO , a menos que também seja uma árvore binária completa.

    O motivo é que, sem a travessia em ordem, você não conseguirá resolver a ambiguidade de esquerda/direita. Por exemplo, as duas árvores binárias abaixo fornecem a mesma travessia pré/pós-ordem:

                    1                   1
               / \                 / \
              2   5       vs      2   5
              \   /              /   /
               3 6              3   6
    • 3

relate perguntas