剑指 Offer 07. 重建二叉树

 有一个很经典的题目就是知道前序和中序求后序这种的，不过这个题是要求直接重建二叉树，但是给了个条件，节点值不重复。

我们可以很容易想到，两个不同的排列出来是这样的：

 我们能在其中看到隐隐约约的递归关系，我们先找出根节点，然后再通过左子树先序和左子树中序重建左子树，依次递归

正是由于节点不重复，所以我们能通过根节点找到中序中的根节点，划分出左子树

递归函数如下：

如果序列长度为0或者不成为序列，返回null，代表x子树为空

如果不返回null，返回一个这样的树，根节点为root，左子树为重建左子树结果，右子树为重建右子树结果

接下来需要设置什么参数，因为是在两个数组上移动，所以参数分别为：

根节点在先序上的位置

中序的范围

class Solution {
    int[] preorder;
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        for(int i=0;i<preorder.length;i++)
        {
            map.put(inorder[i],i);
        }
        return reBuild(0,0,preorder.length-1);
    }
    public TreeNode reBuild(int root,int left,int right)
    {
        if(left>right)
        {return null;}
        TreeNode node=new TreeNode(preorder[root]);
        int num=map.get(preorder[root]);//获得在中序中根节点的序号
        node.left=reBuild(root+1,left,num-1);
        node.right=reBuild(root+num-left+1,num+1,right);
        return node;
    }
}