剑指Offer---根据前序遍历和中序遍历重建二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。代表前序数组，代表中序数组。中序遍历的左右子树比较好找，但是前序遍历的左右子树想到比较难找。

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次重新整理后，代码明显容易读多了。