網頁

2014年3月5日 星期三

POJ 2255 Tree Recovery

想法:
  原本的字串是整棵Tree,我們可先找到這個Tree的Root,再將其分為左右Sub Tree,一直遞迴下去直到Sub Tree只剩一個元素。
  具體做法是:
  1. 先用Preorder String找出Root(P_root),再透過P_root找到Inorder String的Root(I_root)
  2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index:左子樹的左右界和右子樹的左右界),再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
  3. 依照Post Order的順序:
    1. 先遞迴左子樹
    2. 再遞迴右子樹
    3. 輸出Root
底下有附詳細註解的Code: