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

jdk 版本： jdk 1.8

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

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

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

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

public class Solution {
 int currentPosition = 1;
    boolean [] state;
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        TreeNode root = initTreeNode(pre[0]);  //創建根節點
        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) { // 遞歸結束條件
            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);
        // 當前節點在中序遍歷的下一個節點（右邊第1個）是不是已經訪問過了？，是就返回,不是就直接插入當前節點。
        if(temp) {
            return ;
        }
        TreeNode node = initTreeNode(pre[currentPosition]);
        currentNode.right = node;
        mark(in,pre[currentPosition],state);
        currentPosition ++;
        digui(node, pre, in, state);
    }
    // 判斷在中序遍歷中當前節點的下一節點是否訪問過
    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];
    }
    //標記以訪問
    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次解題思路，還是用的遞歸。

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

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

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) {
        //遞歸結束條件
        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;
    }
}

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