Beweisen Sie, dass binäre Bäume mit den gleichen Inorder- und Preorder-Traversalen identisch sind?

Question

Weiß jemand, wie man beweist, dass, wenn zwei binäre Bäume die gleichen Inorder- und Preorder-Traversalen haben, dann sind sie identisch? (Vielleicht durch den zeigt, dass Sie nicht zwei verschiedene binäre Bäume mit identischen Inorder und Preorder Querungen haben können)

Alternativ zeigt einen Fall, der dies widerlegen würde, oder zeigt, warum kann es nicht getan werden?

(Ich gebe zu, das ist rein akademisch, aber es ist keine Hausaufgaben oder nichts. Mein Instinkt sagt mir, dass es wahr ist, aber ich glaube nicht, jemals ich keine Beweise auf Graphen tat.)

Answer 1

der Grund Idee ist, wie man einen binären Baum durch die gegebenen Inorder- und Preorder-Traversalen rekonstruiert.

Es ist möglich, nur einen Binärbaum aus den Inorder- und Preorder-Traversalen zu rekonstruieren.

See:

• Nonrecursive algorithms for reconstructing a binary tree from its traversals (Papier)
• reconstructing a tree from its preorder and postorder lists (SO Frage)