根据二叉树的先序、中序、后序遍历构建二叉树-Java实现

引言：已知一颗二叉树的前序、中序、后序遍历，我们知道如何还原出这颗二叉树，那么我们使用Java代码如何实现？

备注：
根据二叉树的先序、中序、后序遍历构建二叉树-图文详解

 
 class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
 }

	public TreeNode buildTree (int[] preorder, int[] inorder) {
        // write code here
        return buildNode(preorder,0,preorder.length,inorder,0,inorder.length);
    }
    
	private TreeNode buildNode(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight){
        //没有元素了。
        if(inRight - inLeft < 1){
            return null;
        }
        //只有一个元素了。
        if(inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }
        // 前遍历的第一个节点是根节点
        int rootVal = preorder[preLeft];
        TreeNode rootNode = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = 0;
        for (int i = inLeft; i < inRight ; i++) {
            if(inorder[i] == rootVal){
                rootIndex = i;
                break;
            }
        }
        //根据rooIndex划分左右子树
        //划分左右中序数组：根据切割点rootIndex划分中序数组
        //划分左右前序数组：根据中序数组的大小必然是和前序数组的大小是一样的。
        int length = rootIndex - inLeft;
        rootNode.left = buildNode(preorder,preLeft + 1,preLeft + 1 + length,inorder,inLeft,rootIndex);
        rootNode.right = buildNode(preorder,preLeft + 1 + length,preRight,inorder,rootIndex + 1,inRight);
        return rootNode;
    }

	public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        return buildNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    
	private TreeNode buildNode(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight){
        //没有元素了。
        if(inRight - inLeft < 1){
            return null;
        }
        //只有一个元素了。
        if(inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }
        // 后序遍历的最后一个节点是根节点
        int rootVal = postorder[postRight - 1];
        TreeNode rootNode = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndex = 0;
        for (int i = inLeft; i < inRight ; i++) {
            if(inorder[i] == rootVal){
                rootIndex = i;
                break;
            }
        }
        //根据rooIndex划分左右子树
        //划分左右中序数组：根据切割点rootIndex划分中序数组
        //划分左右后序数组：根据中序数组的大小必然是和后序数组的大小是一样的。
        int length = rootIndex - inLeft;
        rootNode.left = buildNode(inorder,inLeft,rootIndex,postorder,postLeft,postLeft + length);
        rootNode.right = buildNode(inorder,rootIndex + 1,inRight,postorder,postLeft + length, postRight - 1);
        return rootNode;
    }