105. 从前序与中序遍历序列构造二叉树（视频讲解！！）

11. （有视频）前序 中序 创建二叉树

原题链接

前序中序构建树

public int preIndex = 0;
private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
    
    //没有了左树 或者 没有了右树
    if(inbegin > inend) {
    
        return null;
    }
    TreeNode root = new TreeNode( preorder[preIndex]);
    //找到当前根节点 在中序遍历中的位置
    int rootIndex = findInorderIndex(inorder, preorder[preIndex],inbegin,inend);
    preIndex++;

    root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);

    root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

    return root;

}

private int findInorderIndex(int[] inorder,int val,int inbegin,int inend) {
    
    for(int i = inbegin;i <= inend;i++) {
    
        if(inorder[i] == val) {
    
            return i;
        }
    }
    return -1;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
    

    return buildTreeChild(preorder,inorder,0,inorder.length-1);

}

1. 递归函数的参数

1. 前序遍历数组，后序遍历数组
2. 后序遍历的 分界角标

2. 每次递归的作用：创建当前节点（前序）构建左右节点（后序）返回当前节点

    TreeNode root = new TreeNode( preorder[preIndex]);
    //找到当前根节点 在中序遍历中的位置
    int rootIndex = findInorderIndex(inorder, preorder[preIndex],inbegin,inend);
    preIndex++;

    root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);

    root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

    return root;

3. 先构建左树，后构建右树（前序先 遍历到左树）

    root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);

    root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);