從今天開始，公眾號陸陸續(xù)續(xù)開始插寫用動畫形式展現(xiàn)算法題，如劍指offer、Leedcode里經(jīng)典面試題型，同時也會更新數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)、網(wǎng)絡原理等知識。

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

1

題目

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

2

基礎(chǔ)鞏固

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

2.1 前序遍歷

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

比如，遍歷一下二叉樹：

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

2.2 中序遍歷

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

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

3

解題思路

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

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

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

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

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

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

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

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

4

測試用例

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

4.1 普通測試

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

4.2 特殊測試

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

4.3 輸入測試

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

5

代碼實現(xiàn)

JavaScript 版本

Java 版本

C 語言版本

Python 版本