[数据结构与算法]力扣（Leetcode）二叉树—105题-从前序中序遍历构建二叉树

105题-从前序中序遍历构建二叉树
题目
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例1：
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

解题思路
1，从前序找到根节点
2，再从中序寻找该根节点索引，分左右两个区间找左右两个子树，[left，right）当前节点的中序结果
具体分析
1，index表示当前处理到前序遍历的哪个位置
2，bulidTreeInternal方法：还原二叉树
TreeNode bulidTreeInternal（int[] preorder,int[] inorder,int left,int right）
（1）边界条件
left>right时表示空树，index > preorder.length时表示当前前序遍历已走完
（2）建立新节点
TreeNode root = new TreeNode(preorder[index]);
index++；向下一节点走
（3）找到中序对应根节点的索引
int pos = find( inorder,left, right,val)
（4）左右子树进行递归
root.left ->bulidTreeInternal(preorder,inorder,left,pos)
root.right->bulidTreeInternal(preorder,inorder,pos+1,right)
代码实现

int index = 0;//当前处理前序遍历到哪个位置
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        return bulidTreeInternal(preOrder,inOrder,0, inOrder.length);
    }
    public TreeNode bulidTreeInternal(int[] preOrder,int[] inOrder,int left,int right){
        if(left >= right){
            return null;
        }
        //当前前序已经走完
        if(index >= preOrder.length){
            return null;
        }
        TreeNode root = new TreeNode(preOrder[index]);
        index++;
        //找到中序遍历根节点对应索引
        int pos = find(inOrder,left,right,root.val);
        //处理左右子树
        root.left = bulidTreeInternal(preOrder,inOrder,left,pos);
        root.right = bulidTreeInternal(preOrder,inOrder,pos+1,right);
        return root;
    }
    //在当前中序遍历中寻找root.val对应的索引值
    public int find(int[] inOrder,int left,int right,int val){
        for(int i = left; i < inOrder.length;i++){
            if(inOrder[i] == val){
                return i;
            }
        }
        return -1;
    }