Tube's World

Q: http://poj.org/problem?id=2255

第一次寫的時候先跳過= =

因為毫無頭緒(不知道要怎麼利用已知preorder和inorder來重建樹)

參考一些網站才知道做法為何

就題目給的範例來說

preorder為: DBACEGF

inorder為: ABCDEFG

因為preorder的第一個data一定為root,所以可以跟inorder中的data做比對

在inorder中找到D之後,就可以將其分成

ABC  D  EFG   這樣

而postorder的順序為(left  right  root)

所以可以利用recursive先去跑D左手邊的data(ABC)

再去跑D右手邊的data(EFG)

每跑一次recursive就找一次root

(利用preorder和inorder去做比對,例如在preorder中D下一個data是B,則B就是ABC三個data的root)

先跑自己的左手邊,再跑自己的右手邊,最後把自己印出來,這就是postorder

pseudo code:

void postorder(int start, int end)

{

    //找root(利用preorder和inorder做比對得知root的index)

    postorder(start, index-1);  //跑左邊遞迴

    postorder(index+1, end);  //跑右邊遞迴

    printf(root);

}

競技程設hw1

POJ的部分終於結束了

果然是門不輕鬆的課 

看來還得繼續加把勁才行