二插樹是數(shù)據(jù)結(jié)構(gòu)里永遠(yuǎn)越不過的一道砍，要想在算法有所提升的話，二插樹是我們必須要攻克的。
今天在編程的時候遇到了，所以在這里記錄儀下免得以后再忘了。
在舉例之前我要先強調(diào)一下，做這種題目的時候你要首先記住，必須記住，絕對要記住的東西：

先序遍歷訪問順序：根->左->右。

中序遍歷訪問順序：左->根->右。

后序遍歷訪問順序：左->右->根。

如果你對這個問題也不是很了接，可以拿紙筆一起來。

之后我們來看例題：
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6

根據(jù)訪問順序：在先序遍歷中第一個數(shù)字，必然是第一個根節(jié)點，我們需要找到1在中序中的位置
1，在第四個位置，那么我們可以斷定在中序中，1的左孩子群就是4，7，2，右孩子群就是5，3，8，6

那現(xiàn)在的結(jié)構(gòu)就是： 1
-----------------------------/ \
剩余未判斷的序列我們來做一個分割：
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6

之后我們怎么判斷左右的孩子群的結(jié)構(gòu)呢？讓我們再來重復(fù)一邊先序和中序的訪問順序：
先序遍歷訪問順序：根->左->右。
中序遍歷訪問順序：左->根->右。

好，那我們繼續(xù)來看先序遍歷中分組的左孩子群。2，4，7。那我們不妨大膽的根據(jù)訪問順序猜測著畫一下：
先序： 2 中序： 7
--------- / \ --------- / \
-------- 4 7 ------- 4 2

這怎么辦呢？，我們不妨從先序的這個類型來著手，畢竟先序遍歷用到的頻率比較高。
就把2當(dāng)作根，剩下我們來看4，7。首先他們肯定不是二的左右孩子，這個根據(jù)訪問順序就能看出，在先序中7在4的后面，那么就把7放在4的子孩子，可究竟是左還是右，這我們還要靠中序的信息來推斷。
中序中，7也在4的左邊，那么根據(jù)訪問順序我們可以斷定：7是右孩子。
先序：根，左，右
中序：左，根，右
我們就把他想象成排序可能，1，2，3和2，1，3。
隨便拿出兩個數(shù)字，看他們的位置：12，13，23 和：21，23，13。
可以看到唯一不同的一組數(shù)就是12和21。
所以12（根左）和21（左根）是逆轉(zhuǎn)的唯一一組，除了這個變化之外其他兩組可以說只要一至，基本上就是正確的結(jié)構(gòu)。
（注：這只是個人總結(jié)的經(jīng)驗，僅供參考）

那么現(xiàn)在推出的結(jié)構(gòu)是： 1
--------------------------------- / \
------------------------------ 2
----------------------------- / \
---------------------------- 4 *
---------------------------- / \
--------------------------- * 7

好現(xiàn)在我們看右半，為了方便我們重新寫一遍序列。
先序：1 | 2，4，7 | 3，5，6，8
中序：4，7，2 | 1 | 5，3，8，6
根據(jù)我們之前的原理，那我們看先序，以3為根，在中序中我們看到5在3的前面。
則我們可以判斷5，為3的左孩子，那只剩下6和8兩個數(shù)了。
這兩個數(shù)列你們看著有沒有種熟悉的感覺？對，就是我剛在說的。兩個數(shù)的位置反轉(zhuǎn)了，
則我們可以得到完整的二插樹了： 1
------------------------------------------------ / \
----------------------------------------------- 2 3
---------------------------------------------- / \ / \
--------------------------------------------- 4 * 5 6
--------------------------------------------- / \ / \
-------------------------------------------- * 7 8 *

其他幾種推斷也是相同的道理，希望對你的學(xué)習(xí)右?guī)椭?/p>

另貼java代碼在下面，攜帶碼的小伙伴可以拿去玩一玩，如果不懂就把輸出全部打出來看：

public class Main {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }

    }
    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};

        TreeNode tn = reConstruction(pre,0,pre.length-1,in,0,in.length-1);
    }

    private TreeNode reConstruction(int[] pre, int i, int length, int[] in, int i1, int length1) {
        if(i>length||i1>length1){
            return null;
        }
        TreeNode node = new TreeNode(pre[i]);
        for(int j =i1;j<=length1;j++){
            if(pre[i]==in[j]){
                node.left = reConstruction(pre,i+1,j+i-i1,in,i1,j-1);
                node.right = reConstruction(pre,j+1+i-i1,length,in,j+1,length1);
                break;
            }
        }
        return node;
    }
}