Tree Reconstruction

問題：只知道一顆樹的 preorder 和 inorder ，要求出樹的架構。
這是個能用 D&C 解決的好問題。在 inorder 之中， root 兩邊分別為左子樹和右子樹；而 preoder 的最左邊的元素就是 root ──故可以利用 root 來分出左子樹和右子樹。每個子樹又是一棵樹，又可以再分割，如此便可求出整棵樹的架構。
能知道分割的關鍵在哪裡，應該就不難理解了。會有唯一解。
至於只有 preorder 和 postorder 的話，是做不出答案的。正是因為這兩個 order 當中，找不到可以分割的地點。
那麼 levelorder 呢？大家就自己想想吧。（ order 的部分可以寫成一篇長長的文章吧。我孤陋寡聞，實在不想多寫。）

這裡也是列出幾題，相信很多人都有看過。

UVa 10701 536 548 10410