壹 ❀ 引
想必凡是接觸過二叉樹算法的同學，在剛上手那會，一定都經歷過題目無從下手，甚至連題解都看不懂的痛苦。由於leetcode不方便調試，題目做錯了也不知道錯在哪裡，最後無奈的cv答案後心裡還不斷安慰自己。不甘心想著要不直接背模板吧，可當天一知半解的記住了，不到半個月回頭面對一道曾做過的簡單二叉樹題，腦袋裡跟看一道新題一樣。
那麼二叉樹對於我這個不是計算機專業的人來說難在哪呢？第一，我始終無法在腦中構建遞歸的過程，就像我的思維空間不足以支撐遞歸在我的腦中運行，大致腦補了兩步就直接亂套了，我想像不出這個過程。
第二，對於二叉樹的前中後層序遍曆始終是一知半解，因為不理解遞歸到底怎麼運行的，所以心裡其實不知道它們三者到底差異在哪，為啥arr.push(root.val)寫的地方不同，就實現了三種不同遍歷方式？小小的腦袋裡留下了大大的疑惑。
const traverse = (root) => {
if (root === null) {
return;
};
// 前序遍歷
traverse(root.left);
// 中序遍歷
traverse(root.right);
// 後序遍歷
}
那麼本文就是為了解答這些疑問而來，我將從遞歸說起，用圖解JS調用棧的方式闡述遞歸思路，幫助大家在腦中構建這個過程，之後再解釋二叉樹前中後序遍歷為什麼邏輯處理的位置不同，就能達到不同差異，那麼本文開始。
貳 ❀ 從遞歸說起
我先來聊聊如何理解遞歸，倘若問你什麼是遞歸？我想大部分人腦袋裡馬上冒出函數自己調用自己就是遞歸，確實沒錯。概念雖然簡單，可是隨手寫一個簡單的遞歸又得思索很久，那麼我們先來總結遞歸的幾個需要注意的點：
- 函數得自己調用自己
- 你只用關注函數第一次調用應該做什麼，不需要關注之後遞歸做什麼，因為遞歸會幫你做第一次相同的操作
- 你需要考慮什麼條件下終止遞歸
- 每次遞歸是否需要設置返回值？不返回能不能解決當前問題
那麼現在問題來了，給一個數組[1, 2, 3]，要求正序輸出數組中的每個元素？很簡單，一個while循環搞定：
const arr = [1, 2, 3];
// 正序遍歷
let i = 0
// 跳出條件
while (i < arr.length) {
// 當前要做什麼？
console.log(arr[i]); // 3 2 1
i++;
};
現在要求用遞歸的方式做相同的操作，我們先將遞歸的幾個要點套到這個for循環中，分析下遞歸時應該做什麼：
- 自己調用自己不用說了，硬性條件
- 每一步只是做console.log(arr[i])以及讓i自增
- 正序遍歷，當i = arr.length時就得跳出遞歸
- 沒有返回值，不需要考慮
思路非常清晰了，現在來用遞歸來實現這個過程：
const traverse = (arr, i = 0) => {
// 跳出條件
if (i >= arr.length) return;
// 第一次調用做什麼？輸出arr[i];
console.log(arr[i]); // 1 2 3
// 自己調用自己
traverse(arr, i + 1);
};
traverse(arr);
我在 一篇文章看懂JS執行上下文中提到，函數每次調用都會創建一個全新的函數上下文，且它們滿足先進後出的特點被存放在JS執行棧中，因為上述遞歸的過程如下：
可以看到一開始執行棧為空，然後遞歸開始，依次創建三個函數進去，直到i === arr.length不滿足條件跳出遞歸，這時候不會繼續創建新的函數調用；
而之前的函數體內只做了console.log(arr[i])一件事，由於不需要繼續創建新的調用，既然執行後完畢了所以開始依次出棧，直到整個調用棧為空，到此整個遞歸結束。
所以為什麼這個遞歸能達到正序輸出的效果呢？其實是因為輸出動作在前，創建新的遞歸在後，我輸出1的時候，輸出2的遞歸都還沒創建呢，當然能正序輸出了。（記住這句話，後面要考）
還是這個數組，現在我們要求倒序輸出它，請你以遍歷和遞歸兩種方式分別實現，怎麼做？我想經過前面的講解，大家不假思索就能寫出如下代碼：
// 倒序遍歷
let i = arr.length - 1;
// i>=0我還能繼續做一件事
while (i >= 0) {
console.log(arr[i]); // 3 2 1
i--;
};
不知道大家有沒有發現，只要我們用while去遍歷一個數組，這個while的操作甚至已經告訴了我們這個倒序遞歸應該怎麼寫：
const traverse = (arr, i = arr.length - 1) => {
// i<0我不能繼續做一件事
if (i < 0) return;
// 第一次調用做什麼？輸出arr[i];
console.log(arr[i]); // 1 2 3 4 5 6
// 自己調用自己
traverse(arr, i - 1);
};
traverse(arr);
因為遞歸是什麼情況下我們不能做一件事，而while是什麼情況下我們能做一件事，因此遞歸的條件總是跟while相反。
那麼到這裡，我們總結了一個很有趣的概念，當你不會寫遞歸時，就想想我用while怎麼遍歷實現，while寫好了，定義一個tarverse函數，然後跳出遞歸的條件與while相反，再將while要做的事情照搬過來，最後加一個函數自調用，遞歸也就完成了，是不是很簡單，這個思路也是模板的一種。
叄 ❀ 執行棧的先進後出
你以為到這就要結束了？當然不，現在問題再升級，同樣還是上面的數組，同樣還是倒序遍歷，但是此時我們要求遞歸的寫法不能跟while一樣讓i遞減，請讓i遞增的同時倒序輸出數組，怎麼做？
還記得上文我是怎麼解釋正序遞歸是為什麼能正序輸出數組的嗎？因為做一件事的動作在遞歸調用之前，這樣就保證了1永遠在2後面先輸出，那怎麼倒序的？很簡單，把你要做的事放在遞歸調用之後即可：
const traverse = (arr, i = 0) => {
if (i >= arr.length) return;
traverse(arr, i + 1);
console.log(arr[i]); // 3 2 1
};
traverse(arr);
為什麼放到後面就能達到倒序遍歷？因為JS的執行棧是先進後出的，我們來解釋下這個過程：
- i=0時，滿足條件，結果遇到了traverse(arr, i + 1)，這時候創建一個新的函數上下文，且這個函數不執行完畢，後面的console.log根本無法執行，所以等著。
- i=1時，同上，又遇到了traverse(arr, i + 1)，繼續創建新的函數上下文，第二個函數的console.log也等著了。
- i=2時，同上，又遇到traverse(arr, i + 1)，繼續創建新的上下文。
- i=3時，不滿足條件直接返回，執行完畢，此時是不是表示i=2的traverse執行完成了，那麼i=2的console.log不就可以執行了，於是第一輸出了3。
- i=2創建的上下文執行完畢，標註i=1的traverse執行完了，它也能執行後面的console.log了
- 於是輸出了3 2 1。
我們要做的事其實是console.log，但是因為traverse(arr, i + 1)在前，遇到就得不斷的創建，導致console遲遲不能觸發直到遞歸跳出。而js執行棧是先進後出，那麼最後進棧的肯定console.log先執行，本質上就是借用了先進後出的後出，來模擬了倒序的過程。
怕大家容易忘記，那到這裡我們先總結下當下學到的知識點：
- 不會寫遞歸？那就寫好while，將while的條件改成相反就是遞歸的跳出條件，因為while是滿足什麼條件做一件事，遞歸是不滿足某個條件不做一件事，之後將while做的事照搬給遞歸即可，這裡不需要考慮這件事應該放在遞歸前還是後。
- i同等自增或自減情況下，可以將做一件事的行為放在遞歸調用的前或者後，便能達到正序或倒序遍歷的效果。
- 正序和倒序的底層差異其實就是執行棧的先進後出，正序是先進（先把事做了再進），倒序是後出（啥也別做先進，出的時候再做一件事）
肆 ❀ 用執行棧看二叉樹前、中、後序遍歷差異
在上文，我們用一個最基本的數組正序，倒序遍歷的例子，解釋了i自增情況下，為什麼console放在遞歸前後位置不同，能達到正序和倒序的效果，其本質原因就是借用了執行棧的先進後出，先做一件事再遞歸，還是先不斷遞歸，出棧的時候再做一件事的區別。
而現在我們再回頭看看文章開頭二叉樹的模板，現在我們來解釋下為什麼一件事丟在三個不同的位置，能達到三種遍歷效果，我們假定有一顆最基本的二叉樹：
很明顯，前序遍歷應該輸出1,2,3，後續遍歷應該輸出2,3,1，中序遍歷應該輸出2,1,3。我們先解釋前序和後續。
前序的的模板可以定義為：
const traverse = (root) => {
if (root === null) {
return;
};
console.log(root.val);
traverse(root.left);
traverse(root.right);
}
由於每個節點都可能會有自己的左右子節點，所以現在這段代碼是不是就非常好理解，我不管你有沒有子節點，到了某個節點咱先輸出，之後再考慮遞歸的事，而traverse(root.left)又在traverse(root.right)之前，所以某個節點的左子節點一定會在右子節點之前輸出。
有同學可能就要想了，如果這顆二叉樹非常複雜呢？我們在文章開頭遞歸處已經說了，你只用考慮當前函數調用應該做什麼，後面遞歸會幫你做相同的事情，即便這顆二叉樹是下圖這樣：
到了節點2，它一樣會讓4,5在3前面輸出，畢竟2,4,5都可以理解成1的左子樹，整體優先級比3高，其實就是這麼個道理。
那麼後序遍歷是怎麼回事呢？後序的代碼其實是這樣：
const traverse = (root) => {
if (root === null) {
return;
};
traverse(root.left);
traverse(root.right);
console.log(root.val);
}
前文已經知道，因為traverse遞歸行為在前，這就導致所有節點沒被遞歸完之前，console一個都會輸出，而因為執行棧先進後出的特色，這就導致子節點的輸出一定比父節點要早（參照前文數組的倒序遍歷），而traverse(root.left)又在traverse(root.right)之前，那麼順序是不是就是(子left節點 > 子right節點) > 父節點，你看不就是這麼一回事，不難理解吧？
有同學可能就馬上想到了，不對吧，按照執行棧先進後出，traverse(roo.left)不是在traverse(root.right)前面先入棧，根據先進後出的規則，後進的應該先輸出才對，那為什麼不是3, 2, 1的輸出，而是2, 3, 1？
首先，子節點肯定早於父節點輸出，我想著點大家肯定沒疑問，接下來我們還是畫圖，解釋這個過程：
首先根節點1，因為它有左右子節點，console肯定沒辦法輸出，我們理解為先進棧存起來。緊接著調用traverse(root.left)
我們也不知道2有沒有子節點，反正也不能立刻輸出，也把2存起來。
注意，那麼此時traverse(root.right)該運行了嗎？我們知道js的同步執行是，某一步邏輯沒跑完，後面的邏輯就得等著前面的邏輯走完，那是不是只要traverse(root.left)沒遞歸完，就輪不到traverse(root.right)運行？
因此，我們繼續判斷讓2的左子節點遞歸，但是很遺憾traverse(2.left)是null，是不是直接return；既然不用繼續遞歸了，那就標明可以運行traverse(2.right)了，結果又是是null導致return，那是不是又能走下一步了，console.log(2)，於是2第一個被輸出了。
於是在3還沒遞歸前，節點2已經出棧了都，由於2（可以理解為1.left）執行完成，那表示終於可以執行1.right也就是節點3了，於是3進棧：
節點3也沒有左右子節點，順利也輸出了3，節點3遞歸結束，也出棧，終於根節點的兩個節點都遞歸完成，是不是根節點的console也能執行了？所以順序就是2,3,1了。
那麼到這裡，我們通過調用棧的形式解釋了二叉樹的前序、後續遍歷。
那麼中序遍歷是怎麼回事呢？通過前文的解釋，大家可以腦補下中序的過程，其實本質差異在於，根節點要做的事情，得左子樹全部遞歸完成，然後左子樹做完了，問根節點，嘿兄弟，你可以做我做的不要事了，然後根節點輸出後，卑微的右子節點接著做。
所謂二叉樹的前中後序遍歷，不就是這麼回事麼。那麼到這裡，我們總結下三種遍歷的區別：
前序遍歷：每個節點都可以理解成一個根節點，在遞歸當前節點左右節點前，咱們先把要做的事情做了。（前序遍歷總是能拿到當前節點信息）
中序遍歷：左子樹遞歸完成，把要做的事情做了，然後根節點才能做相同的事，最後這件事才輪得到右子樹做。
後續遍歷：根節點要做的事往後排一排，左子樹做完右子樹做，最後輪到根節點做。（後續遍歷總是能將子節點信息返回給自己的父節點）
凡是二叉樹遍歷，大家不要一開始就在腦中構建一個非常複雜的樹，跟我一樣，就1, 2, 3三個節點，然後回顧我上面提到的過程，通過這種方式，是不是二叉樹遍歷模板也非常透徹的理解了呢？
伍 ❀ 總
本來想接著講講二叉樹層序遍歷，出於篇幅問題層序遍歷還是留著下篇文章繼續說，那麼通過本文，我們知道了如何通過遞歸遍歷一個數組，以及如何將while改寫成一個遞歸。
之後我們通過執行棧解釋了為什麼將要做的步驟放在遞歸前後能達到正序/倒序遍歷數組結果，從而引出了二叉樹前序、中序、後序遍歷的本質差異，那麼到這裡，我相信你對於遞歸，以及二叉樹的基本遍歷又有了更深入的理解。
原文連結：https://www.cnblogs.com/echolun/p/16216986.html