题解 | #从中序与后序遍历序列构造二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param inorder int整型一维数组 中序遍历序列
     * @param postorder int整型一维数组 后序遍历序列
     * @return TreeNode类
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // write code here

        //先判断是否可操作(长度判0很重要，不然会报错下标越界)
        if (inorder.length != postorder.length || inorder.length == 0) return null;
        //如果只有一个
        if (postorder.length == 1) return new TreeNode(inorder[0]);

        //拿到根节点
        int rootVal = postorder[postorder.length - 1];
        TreeNode node = new TreeNode(rootVal);

        //找到根节点在中序遍历中的位置
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        //存左子树
        int[] left = new int[index];
        int[] leftB = new int[index];
        //存右子树
        int[] right = new int[inorder.length - 1 - index];
        int[] rightB = new int[inorder.length - 1 - index];

        //根据根节点位置分割出中序左子树节点和后序左子树节点
        for (int i = 0; i < index; i++) {
            left[i] = inorder[i];
            leftB[i] = postorder[i];
        }

        //根据根节点位置分割出中序右子树节点和后序右子树节点
        for (int i = index + 1; i < inorder.length; i++) {
            right[i - index - 1] = inorder[i];
        }
        for (int i = index; i < postorder.length - 1; i++) {
            rightB[i - index] = postorder[i];
        }

        node.left = buildTree(left, leftB);
        node.right = buildTree(right, rightB);

        return node;
    }
}