根據先序和中序確定后序的題目,非常經典的數據結構題目。
假如有一棵樹的先序遍歷是DBACEGF,后序遍歷是ABCDEFG。
因為先序遍歷是根節點-左子樹-右子樹,所以可以確定D是這顆樹的根節點。
考慮中序遍歷是左子樹-根節點-右子樹,所以中序的序列被根節點分成了兩個部分,在這里就是ABC和EFG,分別是左子樹和右子樹。
接下來可以確定的以D為根節點的數的左子樹的先序遍歷為BAC(節點個數根據中序的左子樹節點個數確定),右子樹的先序遍歷為EGF.
這樣,我們的問題就轉化成為了與源問題相同的兩個子問題,那么就可以通過遞歸來實現,結束的條件就是子樹只剩一個節點,這個時候先序和中序是一樣的,打印出來,然后return到上一級。
綜上,解決辦法就是現找到根節點,然后根據中序列劃分成兩個部分,然后分別遞歸解決。
需要注意的是,可能出現這樣的狀況:先序為AB,中序為BA;或者先序為AB,中序為AB的情況。即劃分子樹的時候可能右子樹或者左子樹為空。
所以需要加一個判斷,就是是否用來指示序列的左指針已經大于右指針。
POJ 3094 Quicksum實在太水,提一聲就ok。