證明具有相同的inorder和preorder遍歷的二叉樹是相同的？

Question

有沒有人知道如何證明，如果兩棵二叉樹有相同的順序和前序遍歷，那麼它們是相同的？ （也許通過顯示你不能有兩種不同的二叉樹，它們具有相同的順序和順序遍歷）

或者，顯示一個可能會反駁這種情況的案例，或者說明爲什麼不能這樣做？

（我承認，這是純學術的，但它不是功課什麼的。我的直覺告訴我，這是真的，但我不認爲我做過的圖表任何證據。）

Answer 1

基本想法是如何通過給定的inorder和preorder遍歷來重構二叉樹。

可以重建只有一個二叉樹的順序和前序遍歷。

參見：

• Nonrecursive algorithms for reconstructing a binary tree from its traversals（紙）
• reconstructing a tree from its preorder and postorder lists（SO問題）