通过中序遍历和前序遍历，后续遍历来构建二叉树

通过前序遍历和中序遍历构建二叉树
用中序遍历的根节点和第一个左节点获取做节点长度，右节点下标。
通过前序遍历(第一个节点)和后续遍历(最后一个节点)得到根节点

    public class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
    
            val = x;
        }
    }

    /** * 通过前序遍历和中序遍历构建二叉树，前提树节点值不重复 * * @param pre 前序遍历的结果 * @param preRootNodeStart 前序遍历开始根节点下标 * @param preEnd 前序遍历集合最后一个下标 * @param inLeftNodeStart 中序遍历第一个左节点下标 * @param inPos 中序遍历值与下标映射关系 * @return */
    private TreeNode buildTree(int[] pre, int preRootNodeStart, int preEnd, int inLeftNodeStart, Map<Integer, Integer> inPos) {
    
        if (preRootNodeStart > preEnd) return null;
        TreeNode root = new TreeNode(pre[preRootNodeStart]);
        // 获取根节点在中序遍历的下标
        int rootIdx = inPos.get(pre[preRootNodeStart]);
        // 获取左子树的长度
        int leftLen = rootIdx - inLeftNodeStart;
        root.left = buildTree(pre, preRootNodeStart + 1, preRootNodeStart + leftLen, inLeftNodeStart, inPos);
        root.right = buildTree(pre, preRootNodeStart + leftLen + 1, preEnd, rootIdx + 1, inPos);
        return root;
    }

    public TreeNode buildTree(int[] pre, int[] in) {
    
        Map<Integer, Integer> inPos = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
    
            inPos.put(in[i], i);
        }
        return buildTree(pre, 0, pre.length - 1, 0, inPos);
    }
	    private TreeNode buildTreePrePostArray(int[] post, int postStart, int postEnd, int inStart, Map<Integer, Integer> inPos) {
    
        if (postStart > postEnd) return null;
        TreeNode root = new TreeNode(post[postEnd]);
        int rootIdx = inPos.get(post[postEnd]);
        int leftLen = rootIdx - inStart;
        root.left = buildTreePrePostArray(post, postStart, postStart + leftLen - 1, inStart, inPos);
        root.right = buildTreePrePostArray(post, postStart +leftLen, postEnd - 1, rootIdx + 1, inPos);
        return root;
    }

    // Time: O(n). Space:O(n)
    public TreeNode buildTreePrePostArray(int[] in, int[] post) {
    
        Map<Integer, Integer> inPos = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
    
            inPos.put(in[i], i);
        }
        return buildTreePrePostArray(post, 0, post.length - 1, 0, inPos);
    }