摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。代表前序數(shù)組，代表中序數(shù)組。中序遍歷的左右子樹比較好找，但是前序遍歷的左右子樹想到比較難找。

jdk 版本： jdk 1.8

題目：
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

解題思路：
對于樹的操作來說，不管是遍歷還是建樹，首先想到的應(yīng)該是用遞歸算法來解。

第一次嘗試的思路大概是這樣的：
前序數(shù)組的第1個元素即是樹的根節(jié)點。關(guān)鍵在于怎么確定樹的左右子樹。
例如：
在此聲明幾個變量。pre：代表前序數(shù)組，in：代表中序數(shù)組。
假設(shè)當(dāng)前遍歷到pre的第2個元素，即根節(jié)點的下一個元素。在in中判斷第2個元素跟當(dāng)前節(jié)點（即根節(jié)點）的大小。
如果在in中第2個元素的位置小于當(dāng)前節(jié)點的位置，那么可以判定，當(dāng)前此節(jié)點是當(dāng)前節(jié)點的左子樹，當(dāng)然，前提是當(dāng)前節(jié)點左子樹為空。
否則，可能是當(dāng)前節(jié)點的右子樹。（注意是可能。）
關(guān)鍵： 如何判斷是不是當(dāng)前節(jié)點的右子樹？
即當(dāng)前節(jié)點在in中的位置的下一個元素是不是被訪問過，如果沒有被訪問過，即是右子樹，否則不是，應(yīng)當(dāng)返回。

下面貼出我第一次嘗試的代碼。（可以過）

public class Solution {
 int currentPosition = 1;
    boolean [] state;
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        TreeNode root = initTreeNode(pre[0]);  //創(chuàng)建根節(jié)點
        TreeNode currentNode = root;
        state = new boolean [pre.length];
        for(int i = 0 ; i < pre.length; i++) {
            if(in[i] == pre[0]) {
                state[i] = true;
            }else {
                state[i] = false;
            }
        }
        digui(currentNode,pre,in,state);
        return root;
    }
 
    public void digui(TreeNode currentNode,int [] pre,int [] in,boolean [] state) {
        if(currentPosition >= pre.length) { // 遞歸結(jié)束條件
            return ;
        }
        int parentVal = currentNode.val;
        int nextVal = pre[currentPosition];
        if(findPosition(parentVal,nextVal,in)) { //左邊
            TreeNode node = initTreeNode(nextVal);
            if(currentNode.left == null) {
                currentNode.left = node;
                mark(in,pre[currentPosition],state);
                currentPosition ++;
            }
            digui(node, pre, in, state);
        }
        //右邊
        boolean temp = isRightVisit(parentVal, in, state);
        // 當(dāng)前節(jié)點在中序遍歷的下一個節(jié)點（右邊第1個）是不是已經(jīng)訪問過了？，是就返回,不是就直接插入當(dāng)前節(jié)點。
        if(temp) {
            return ;
        }
        TreeNode node = initTreeNode(pre[currentPosition]);
        currentNode.right = node;
        mark(in,pre[currentPosition],state);
        currentPosition ++;
        digui(node, pre, in, state);
    }
    // 判斷在中序遍歷中當(dāng)前節(jié)點的下一節(jié)點是否訪問過
    private boolean isRightVisit(int parentVal, int[] in,boolean [] state){
        int temp = 0;
        for(int i = 0; i < in.length; i++) {
            if(in[i] == parentVal) {
               temp = i + 1;
                break;
            }
        }
          return state[temp == in.length? temp -1 : temp];
    }
    //標(biāo)記以訪問
    private void mark(int [] in, int markVal,boolean [] state) {
        for(int i = 0; i < in.length; i++) {
            if(in[i] == markVal) {
                state[i] = true;
            }
        }
    }
 
    //在左邊返回ture,在右邊返回false
    private boolean findPosition(int parent, int son,int [] in) {
        int pTemp = 0;
        int sTemp = 0;
        for(int i = 0; i < in.length; i++) {
            if(in[i] == parent) {
                pTemp = i;
            }else if(in[i] == son) {
                sTemp = i;
            }
        }
        return sTemp < pTemp;
    }
    //初始化TreeNode
    private TreeNode initTreeNode(int val) {
        TreeNode node = new TreeNode(val);
        node.left = null;
        node.right = null;
        return node;
    }
}

看了上面代碼，又臭又長。 一般對于遞歸算法，是沒有必要寫這么長的代碼。重新思考一下，
整理出第2次解題思路，還是用的遞歸。

思路：
遍歷前序數(shù)組，從中序數(shù)組中，找到當(dāng)前遍歷的元素，那么左邊的肯定是當(dāng)前節(jié)點的左子樹，右邊的肯定是當(dāng)前節(jié)點的右子樹。那么直接遞歸即可。
中序遍歷的左右子樹比較好找，但是前序遍歷的左右子樹想到比較難找。
解釋一下，遞歸左子樹中的 startPre + i - startIn 。
（i - startIn ),是通過中序遍歷找到左子樹的偏移量（因為中序遍歷中，在當(dāng)前節(jié)點的左邊的，那就是當(dāng)前節(jié)點的左子樹），再加上startPre,即找到在前序遍歷的左子樹的最后一個節(jié)點。

上面理解了，那么理解 startPre + i - startIn + 1。就簡單多了。
在前序遍歷中，當(dāng)前節(jié)點左子樹的最后一個節(jié)點的下一個節(jié)點肯定是右子樹的起始節(jié)點。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    private TreeNode reConstructTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
        //遞歸結(jié)束條件
        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);
         
        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
                //左子樹
                root.left=reConstructTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                //右子樹
                root.right=reConstructTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
            }
                 
        return root;
    }
}

總結(jié)： 第一次寫出那么長的代碼，其實是對遞歸的思想不大懂，第2次重新整理后，代碼明顯容易讀多了。