從今天開始，公眾號陸陸續續開始插寫用動畫形式展現算法題，如劍指offer、Leedcode里經典面試題型，同時也會更新數據結構與算法基礎、網絡原理等知識。

以為無論是面試還是實際項目，對算法的要求也非常的嚴格，所以小鹿盡最大努力把算法還原成動畫形式來講解，爭取讓每個人都能看懂算法、學會算法。

1

題目

已知前序遍歷為{1,2,4,7,3,5,6,8}，中序遍歷為{4,7,2,1,5,3,8,6}，它的二叉樹是怎么樣的？

2

基礎鞏固

根據上述題目所述，我們已知前序遍歷和中序遍歷，回顧一下，什么是前序遍歷？什么是中序遍歷？

2.1 前序遍歷

前序遍歷一顆二叉樹，首先輸出根節點，然后輸出左子節點，最后輸出右子節點。

比如，遍歷一下二叉樹：

顏色變深表示遍歷，突出表示輸出

2.2 中序遍歷

中序遍歷一棵二叉樹，首先輸出左子節點，然后輸出輸出根節點，最后右子節點。

以上邊二叉樹為例，通過中序遍歷輸出。

3

解題思路

既然我們知道了二叉樹如何進行前序遍歷和中序遍歷了，那么已知前序遍歷和中序遍歷如何反推二叉樹呢？

那么問題來了，只知道前序遍歷能不能反推二叉樹呢？我們就試一下，比如題目中所述，{1,2,4,7,3,5,6,8}，根據前序遍歷，根、左、右，1 肯定是 根節點，那么一下2,4,7.....哪些是左子節點呢？左子節點有幾個呢？很顯然我們是不知道的，由此可以得出，只知道前序遍歷是不可能反推出二叉樹的，中序遍歷也是如此，自己可以嘗試一下。

那么前序遍歷和中序遍歷可不可以？那我們要試一下，我們上邊通過前序遍歷找到第一個根節點就是 1，如圖

中序遍歷{4,7,2,1,5,3,8,6}的規律又是左、根、右，所以 1 結點在中序遍歷中為根，它的左邊就是所有左子節點4,7,2，右邊為所有的右子節點5,3,8,6。

此時我們已經劃分左右子節點了，但是左邊的子節點中哪些又是根節點呢？我們再回到前序遍歷中，根據前序遍歷的特點，根、左、右，在從子節點進行劃分，那么 1 結點中的子節點誰為根節點呢？

我們一眼就能看出來，就是 2 結點，那么剩余的 4,7 左右結點怎么分呢？我們根據上述再回到中序遍歷，找到 2 根節點，根據中序遍歷左、根、右的特點，找到 2 結點，那左邊的就是左子節點，右邊的就是右子節點，我們可以看到，左邊有兩個數，正是 4 和 7 結點。

右邊只有 1 結點，1 結點我們剛剛說了，是根節點，所以以 2 為根節點是沒有右子節點的，剩下的數字也是同樣的方式區分，自己可以試一下，動手畫一畫。

我們仔細發現，其實整個層層往下，以及左右，都是相同的解決方式，而且大問題可以分解為小問題，我們下意識就應該想起小鹿之前分享過的知識，那就是遞歸，既然是遞歸，就應該有終止條件，終止條件就是當子節點為空時，此時遞歸結束。

4

測試用例

我們之前的文章強調過，手寫代碼之前，一定先把測試用例想好，為了能夠在手寫代碼的時候考慮到邊界情況，還為了防止你到時候面試涂涂改改。

4.1 普通測試

完全二叉樹、非完全二叉樹。

4.2 特殊測試

只有左子節點二叉樹，只有右子節點、只有一個結點的二叉樹 —— 特殊二叉樹測試。

4.3 輸入測試

空樹、空指針null、前序和中序不匹配。

5

代碼實現

JavaScript 版本

Java 版本

C 語言版本

Python 版本