1. 从中序和后序遍历构造二叉树

力扣106
题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。你可以假设树中没有重复的元素。
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7

class Solution {
    int[] inorder;//因为在creatTree方法中用到这两个数组变量了
    int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();

    //前序负责找根，中序负责分割
    public TreeNode creatTree(int ol, int or, int pl, int pr){
        if(ol > or) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int index = map.get(preorder[pl]);
        root.left = creatTree(ol, index - 1, pl + 1,pl + index - ol);
        root.right = creatTree(index +1, or, pl + index - ol +1 , pr);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.inorder = inorder;
        this.preorder = preorder;
        //先把中序加入哈希表中
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return creatTree(0, inorder.length - 1, 0, preorder.length - 1);
    }
}

2. 从前序和中序构建二叉树

力扣105，剑指offer7
题目要求：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7

class Solution {
    int[] inorder;//因为在creatTree方法中用到这两个数组变量了
    int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();

    //前序负责找根，中序负责分割
    public TreeNode creatTree(int ol, int or, int pl, int pr){
        if(ol > or) return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int index = map.get(preorder[pl]);
        root.left = creatTree(ol, index - 1, pl + 1,pl + index - ol);
        root.right = creatTree(index +1, or, pl + index - ol +1 , pr);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.inorder = inorder;
        this.preorder = preorder;
        //先把中序加入哈希表中
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return creatTree(0, inorder.length - 1, 0, preorder.length - 1);
    }
}

3.由前序和后序构建二叉树

力扣889
题目描述：返回给定的前序和后序遍历匹配的任何二叉树。（不唯一，任何一个答案即可）
pre 和 post 遍历中的值是不同的正整数。
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

class Solution {
    int[] pre;
    int[] post;
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode creatTree(int pre_l, int pre_r, int post_l, int post_r){
        if(pre_l > pre_r) return null;
        TreeNode root = new TreeNode(pre[pre_l]);
        if(pre_l == pre_r) return root;  //数组要提前结束，否则后面pre[pre_l+1]数组会溢出越界
        //前序根节点后面的这个节点一定是下一层的一个小根节点，用来分割后序(与其他两题的区别)
        int index = map.get(pre[pre_l + 1]);
        root.left = creatTree(pre_l + 1, pre_l+1+index-post_l, post_l, index);
        root.right = creatTree(pre_l+1+index-post_l+1, pre_r, index+1, post_r);
        return root;
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.pre = pre;
        this.post = post;
        for(int i = 0;i < post.length; i++){
            map.put(post[i], i);
        }
        return creatTree(0, pre.length - 1, 0, post.length - 1);
    }
}

总结 1-3 ： 三种遍历两两结合，重构二叉树的过程。
只有在前后序结合时，需要考虑一下数组越界的问题(代码中已指出)
其他两种只需要正常考虑边界范围即可