题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这部分我在本题基础上加了遍历方法，可以在编辑器运行，看结果

import java.util.ArrayList;
import java.util.List;

/**
 * @author 周利盘特
 * @version 1.0
 */
public class BuildTree {
    public static void main(String[] args) {
        int[] inOrder = {9, 3, 15, 20, 7};//二叉树中序遍历序列
        int[] postOrder = {9, 15, 7, 20, 3};
        TreeNode treeNode = buildTree(inOrder, postOrder);
        List<Integer> tree = showTree(treeNode, new ArrayList<Integer>());
        System.out.println(tree.toString());
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        //如果数组为0，返回空
        if (inorder.length == 0) {
            return null;
        }
        //将后续遍历数组的最后一个元素作为根节点
        int value = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(value);
        if (postorder.length == 1) {//若数组只有一个节点，就返回这棵树
            return root;
        }
        //以后续遍历数组的最后一个节点为分割点，
        int despitIndex;
        for (despitIndex = 0; despitIndex < inorder.length; despitIndex++) {
            if (inorder[despitIndex] == root.val) {
                break;
            }
        }
        //分割中序遍历数组，分成左中序数组，右中序数组
        int[] leftInorder = new int[despitIndex];
        for (int i = 0; i < leftInorder.length; i++) {
            leftInorder[i] = inorder[i];
        }
        int[] rightInorder = new int[inorder.length - leftInorder.length - 1];
        for (int i = despitIndex + 1, j = 0; i < inorder.length; i++, j++) {
            rightInorder[j] = inorder[i];
        }
        //分割后序遍历数组之前，将后序遍历数组最后一个元素去掉，因为已经作为根节点了
        int[] tempPost = new int[postorder.length - 1];
        for (int i = 0; i < tempPost.length; i++) {
            tempPost[i] = postorder[i];
        }
        postorder = tempPost;//去掉了最后一个元素
        //分割后续遍历数组，分成左后序数组，右后序数组
        int[] leftPostorder = new int[leftInorder.length];
        for (int i = 0; i < leftInorder.length; i++) {
            leftPostorder[i] = postorder[i];
        }
        int[] rightPostorder = new int[postorder.length - leftPostorder.length];
        for (int i = leftPostorder.length, j = 0; i < postorder.length; i++, j++) {
            rightPostorder[j] = postorder[i];
        }
        root.left = buildTree(leftInorder, leftPostorder);
        root.right = buildTree(rightInorder, rightPostorder);
        return root;
    }

    /**
     * 前序遍历二叉树
     * @param root 二叉树根节点
     * @param list 存放遍历的节点
     * @return     遍历结果
     */
    public static List<Integer> showTree(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.val);
        }
        if (root.left != null) {
            showTree(root.left, list);
        }
        if (root.right != null) {
            showTree(root.right, list);
        }
        return list;
    }
}

/**
 * 二叉树操作类
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}