根據(jù)先序和中序確定后序的題目，非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)題目。
假如有一棵樹(shù)的先序遍歷是DBACEGF，后序遍歷是ABCDEFG。
因?yàn)橄刃虮闅v是根節(jié)點(diǎn)－左子樹(shù)－右子樹(shù)，所以可以確定D是這顆樹(shù)的根節(jié)點(diǎn)。
考慮中序遍歷是左子樹(shù)－根節(jié)點(diǎn)－右子樹(shù)，所以中序的序列被根節(jié)點(diǎn)分成了兩個(gè)部分，在這里就是ABC和EFG,分別是左子樹(shù)和右子樹(shù)。
接下來(lái)可以確定的以D為根節(jié)點(diǎn)的數(shù)的左子樹(shù)的先序遍歷為BAC（節(jié)點(diǎn)個(gè)數(shù)根據(jù)中序的左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)確定），右子樹(shù)的先序遍歷為EGF.
這樣，我們的問(wèn)題就轉(zhuǎn)化成為了與源問(wèn)題相同的兩個(gè)子問(wèn)題，那么就可以通過(guò)遞歸來(lái)實(shí)現(xiàn)，結(jié)束的條件就是子樹(shù)只剩一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候先序和中序是一樣的，打印出來(lái)，然后return到上一級(jí)。
綜上，解決辦法就是現(xiàn)找到根節(jié)點(diǎn)，然后根據(jù)中序列劃分成兩個(gè)部分，然后分別遞歸解決。
需要注意的是，可能出現(xiàn)這樣的狀況：先序?yàn)锳B,中序?yàn)锽A；或者先序?yàn)锳B,中序?yàn)锳B的情況。即劃分子樹(shù)的時(shí)候可能右子樹(shù)或者左子樹(shù)為空。
所以需要加一個(gè)判斷，就是是否用來(lái)指示序列的左指針已經(jīng)大于右指針。
POJ 3094 Quicksum實(shí)在太水，提一聲就ok。