前言

前面三篇文章用三种方式进行了二叉树的三种遍历，前序，中序，后序，今天反过来，通过前序和中序的遍历结果，重新构建出一颗二叉树，此题也是leetcode上的105题。

//根据一棵树的前序遍历与中序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
// Related Topics 树 深度优先搜索 数组

首先还是分析一下前序和中序遍历的特点

1、前序遍历中，第一个遍历结果是二叉树的根节点；
2、中序遍历中，根节点的左侧遍历结果是二叉树的左子树，根节点右侧遍历结果是二叉树的右子树。

那么我们用例题来做一下验证

前序遍历结果：[3,9,20,15,7] ，第一个遍历元素是3，是二叉树的根节点；
中序遍历结果：[9,3,15,20,7] ，3的左边[9]，是二叉树的左子树，[15,20,7]是二叉树的右子树。

因而，我们可以找到此题的解法：

1、找到二叉树的根节点rootNode(eg：3)
2、找到rootNode在中序遍历中的位置（eg：3的下表是1）
3、找到左子树前序和中序遍历结果区间(eg：左子树前序：[9]，左子树中序：[9])
4、找到右子树前序和中序遍历结果区间(eg：左右树前序：[20,15,7]，左子树中序：[15,20,7])
5、构建二叉树并返回。

区间的寻找有几点细节

1、左子树前序区间是[根节点前序遍历下标+1，根节点前序下标+左子树长度]
2、左子树中序区间是[根节点中序区间起始点，根节点中序区间位置-1]
3、右子树前序区间是[根节点前序下标+左子树长度+1，根节点前序区间终点]
4、右子树中序区间是[根节点中序区间位置+1，根节点中序区间终点]

以此，代码如下

class Solution {

    private Map<Integer, Integer> inorderValue2IndexMap = new HashMap();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int size = preorder.length;
        for (int i = 0; i < inorder.length; i++) {
            // 将中序遍历结果的值和index建立映射关系，方便寻找各节点中序下标
            inorderValue2IndexMap.put(inorder[i],i);
        }
        return buildTree(preorder,inorder,0,size-1,0,size-1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
        // 1 判断是否没有左子树或右子树
        if (preorderEnd < preorderStart) {
            return null;
        }
        // 2 构造当前节点，前序遍历区间第一个值就是当前节点的值
        int rootValue = preorder[preorderStart];
        TreeNode rootNode = new TreeNode(rootValue);
        // 3 找到左子树区间 构建左子树
        int inorderIndex = inorderValue2IndexMap.get(rootValue);
        int leftCount = inorderIndex - inorderStart;
        TreeNode leftNode = buildTree(preorder, inorder, preorderStart + 1, preorderStart + leftCount, inorderStart, inorderIndex - 1);
        rootNode.left = leftNode;
        // 4 找到右子树区间 构建右子树
        TreeNode rightNode = buildTree(preorder, inorder, preorderStart + leftCount + 1, preorderEnd, inorderIndex + 1, inorderEnd);
        rootNode.right = rightNode;
        // 5 返回
        return rootNode;
    }
}