根据前序、中序遍历构造二叉树 and 根据中序、后序遍历构造二叉树

1. 根据一棵树的前序遍历与中序遍历构造二叉树

(ps：题目链接）105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

  给你两个序列，preorder和 inorder ， preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，构造出二叉树并返回其根节点。

  来看看二叉树的前序遍历与中序遍历的特点是什么。

前序遍历：

  前序遍历的第一个节点是二叉树的根节点，然后是左子树的节点，最后是右子树的节点。

中序遍历：

  中序遍历的前一部分是左子树的节点，中间是根节点，最后是右子树的节点。

  因为是同一个二叉树，所以这两种序列的左子树节、右子树节点是相同的，这时我们就可以通过递归的方式来创建这个二叉树。

  怎么递归呢？因为前序序列的第一个节点是根节点，我们拿到第一个节点然后在中序序列中找到该节点的位置，用该节点的左边来创建左子树、右边来创建右子树，然后以它们的子区间用相同的步骤来创建。

按照上面的思路，我们需要将区间的范围给表示出来，以方便递归：

//根据一棵树的前序遍历与中序遍历构造二叉树

//preorder为前序序列，inorder为后序序列。
public TreeNode buildTree(int[] preorder, int[] inorder) {
    //开始的区间是 前序：0~preorder.length  中序：0~inorder.length
    return buildTreeChild(preorder,0,preorder.length-1,inorder,0,inorder.length - 1);
}

public TreeNode buildTreeChild(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight){
    //当没有子树的时候
    if(preLeft > preRight || inLeft > inRight){
        return null;
    }
    //创建根节点，preorder[preLeft] 为根节点
    TreeNode root = new TreeNode(preorder[preLeft]);
    //查找 中序序列中的根节点位置
    int rootIndex = findIndex(inorder,inLeft,inRight,preorder[preLeft]);

    //对左子树序列进行递归创建，连接左子树
    // 前序：（preLeft + 1，rootIndex - inLeft + preLeft） 中序：（inLeft，rootIndex - 1）
    root.left = buildTreeChild(preorder,preLeft + 1,rootIndex - inLeft + preLeft,inorder,inLeft,rootIndex - 1);
    //对右子树序列进行递归创建，连接右子树
    // 前序：（rootIndex - inLeft + preLeft + 1，preRight） 中序：（rootIndex + 1 ，inRight）
    root.right = buildTreeChild(preorder,rootIndex - inLeft + preLeft + 1,preRight,inorder,rootIndex + 1,inRight);
    return root;
}

//查找根节点在中序中的下标
public int findIndex(int[] inorder,int inLeft,int inRight,int val){
    for(int i = inLeft;i <= inRight;i++){
        if(inorder[i] == val){
            return i;
        }
    }
    return -1;
}

  这里的查找根节点在中序中的下标可以用哈希表来优化（可以去看官方答案），这里就不演示了。

2. 根据一棵树的中序遍历与后序遍历构造二叉树

(ps：题目链接）106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

  跟上面的方法一模一样，只不过是位置换了一下。

  后序遍历就是最后一个节点为树的根节点，以此来在中序中寻找根节点的位置来划分左右子树。

public int findIndex(int[] inorder,int inLeft,int inRight,int val){
    for(int i = inLeft;i <= inRight;i++){
        if(inorder[i] == val){
            return i;
        }
    }
    return -1;
}


//根据一棵树的中序遍历与后序遍历构造二叉树
public TreeNode buildTree(int[] inorder, int[] postorder) {
    return buildTreeChild(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1);
}
public TreeNode buildTreeChild(int[] inorder,int inLeft,int inRight,int[] postorder,int posLeft,int posRight){
    if(inLeft > inRight || posLeft > posRight){
        return null;
    }
    
    //查找 中序序列中的根节点位置
    int rootIndex = findIndex(inorder,inLeft,inRight,postorder[posRight]);
    //创建根节点
    TreeNode root = new TreeNode(postorder[posRight]);
    //对左子树序列进行递归创建，连接左子树
    root.left = buildTreeChild(inorder,inLeft,rootIndex - 1,postorder,posLeft,rootIndex - inLeft + posLeft- 1);
    //对右子树序列进行递归创建，连接右子树
    root.right = buildTreeChild(inorder,rootIndex + 1,inRight,postorder,rootIndex - inLeft + posLeft,posRight- 1);
    return root;
}

  当然，这里的查找中序序列中的根节点位置也可以用哈希，大家自己去试一试。

（ps：如有错误，请在评论区指出，谢谢🌹）