二叉樹(shù)有前序，中序，后序三種遍歷順序。初學(xué)者很容易混淆。記住以下兩個(gè)關(guān)鍵點(diǎn)就很好理解。
三種順序的共同點(diǎn)：左右的順序是不變的。
三種順序的不同點(diǎn)：所謂的前中后序，說(shuō)的是root節(jié)點(diǎn)的位置在前，中，后。先序是root,左,右；中序是左,root,右；后序的順序是左，右，中。基于以上兩點(diǎn)記憶就非常簡(jiǎn)單了。
遞歸序的后序遍歷，即自定義的代碼邏輯在左右遞歸結(jié)束后執(zhí)行。通用的偽代碼框架結(jié)構(gòu)如下：
public static int recursion(TreeNode node){
if(node==null){
return 0;
}
//前序遍歷
//代碼邏輯
int left = recursion(node.left)；
//中序遍歷 代碼邏輯
int right = recursion(node.left)；
//后序遍歷
//代碼邏輯如下：
return left+right+node.data;
}
剛開(kāi)始學(xué)遞歸，腦袋中一模擬方法中調(diào)用方法，腦袋就會(huì)炸鍋，瞬間感覺(jué)腦細(xì)胞不夠用了。其實(shí)可以換一個(gè)角度，放棄從root節(jié)點(diǎn)開(kāi)始模擬，而是從最后一層葉子節(jié)點(diǎn)逆著模擬遞歸調(diào)用過(guò)程。
后序遍歷從執(zhí)行開(kāi)始，代碼到 int left = recursion(node.left) 部分就會(huì)開(kāi)啟新的壓棧，這個(gè)過(guò)程一直會(huì)持續(xù)到什么時(shí)候呢？答案是最終的葉子節(jié)點(diǎn)。
如果現(xiàn)在的入?yún)⑹侨~子節(jié)點(diǎn)，則node.left =null ,node.right=null 那么執(zhí)行遞歸函數(shù)后，都會(huì)返回0，即int left= 0，int right = 0；因?yàn)闀?huì)判斷入?yún)閚ull,返回，不再繼續(xù)開(kāi)啟新的堆棧了。
重點(diǎn)來(lái)了，跨過(guò)了前邊兩個(gè)坎兒
int left = recursion(node.left)；
int right = recursion(node.left)；
最終才會(huì)執(zhí)行到 return left+right+node.data部分，也就是自定義代碼這里。
葉子節(jié)點(diǎn)執(zhí)行完了，因?yàn)榈谝淮握{(diào)用這個(gè)方法的都是int left = recursion(node.left)；所以會(huì)返回上一個(gè)堆棧記錄的地址，接著執(zhí)行上一個(gè)堆棧中的int right = recursion(node.left)；以此往復(fù)，最終回到根結(jié)點(diǎn)root 再次執(zhí)行return left+right+node.data;
所以，后序遍歷的難點(diǎn)就是，只有到了葉子節(jié)點(diǎn)部分，才會(huì)完整執(zhí)行一次我們上邊寫(xiě)的自定義代碼。其他部分都是只開(kāi)堆棧，不執(zhí)行邏輯。
葉子節(jié)點(diǎn)時(shí)候，才會(huì)跳過(guò)左右繼續(xù)遞歸這兩個(gè)坎兒，第一次執(zhí)行返回操作。其他高一層級(jí)的調(diào)用，都是大爺，懶得要死，兒子不干完活兒返回結(jié)果，你休想叫醒他，讓他干一點(diǎn)活。但好處也是，一旦有返回結(jié)果了，他就自動(dòng)執(zhí)行了。這就是后序遍歷的特點(diǎn)，高一級(jí)的依賴第低一級(jí)的返回結(jié)果。這么一說(shuō)，有感覺(jué)了吧！
下邊這張圖展示了執(zhí)行順序
從root節(jié)點(diǎn)開(kāi)始，一直執(zhí)行藍(lán)色的，直到最后一個(gè)藍(lán)色節(jié)點(diǎn)是null為止。返回到第二個(gè)藍(lán)色節(jié)點(diǎn)，執(zhí)行黃色點(diǎn)的遞歸方法，執(zhí)行完后，返回到當(dāng)前的節(jié)點(diǎn)，即倒數(shù)第二個(gè)藍(lán)色節(jié)點(diǎn)，再返回，到達(dá)倒數(shù)第三個(gè)節(jié)點(diǎn)。。。以此類推
倒數(shù)第三個(gè)節(jié)點(diǎn)也是先執(zhí)行藍(lán)色，結(jié)束后回到黃色節(jié)點(diǎn)的方法體內(nèi)，再執(zhí)行紅色遞歸調(diào)用，結(jié)束后再次回到黃色節(jié)點(diǎn)，執(zhí)行黃色節(jié)點(diǎn)的自定義代碼，之后再返回，達(dá)到倒數(shù)第三個(gè)節(jié)點(diǎn)
