剑指Offer07：重建二叉树（Java）

题目描述：

解法思路：
    一开始想了半个小时都没想出来，幸好得到大佬的帮助，终于做出来，嘻嘻。
    采用递归的思想，不断拆分左右子树即可。首先我们通过前序遍历可以看到这个树的根节点是3，然后通过中序遍历，我们可以知道9是左子树，15，20，7是右子树。所以一开始我们使用一个map集合存放中序遍历的数组元素和索引值。当通过前序遍历知道根节点后，通过map集合查询获得根节点在中序遍历数组的位置，那么它左边的元素是左子树，右边的元素是右子树。
    我们可以看到左子树的根节点，是在根节点下个位置。而右子树的根节点，是在根节点加上左子树元素个数的下个位置。每层的树，我们还应该设置它的左右边界。每下一层，边界也随之改变。当遍历到叶子节点时候，左边界大于右边界时，return null就可以结束递归条件啦。

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer,Integer> inordermap=new HashMap<>();
    private int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        for(int i=0;i<inorder.length;i++){
            inordermap.put(inorder[i],i);
        }
        return bianli(0,0,inorder.length-1);
    }

    TreeNode bianli(int root,int leftline,int rightline){
        if(leftline>rightline) return null;
        TreeNode node=new TreeNode(preorder[root]);
        node.left=bianli(root+1,leftline,inordermap.get(preorder[root])-1);
        node.right=bianli(root+inordermap.get(preorder[root])-leftline+1,inordermap.get(preorder[root])+1,rightline);
        return node;
    }
}

执行结果：