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