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

中序遍历：左根右；后序遍历：左右根

从后序遍历中拿出根节点，去中序遍历中分割数组，然后根据中序左右子树数目分割后序

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类
     */
    
    Map<Integer, Integer> map;
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        TreeNode root = split(inorder, 0, inorder.length, postorder, 0, postorder.length);
        return root;
    }

    private TreeNode split(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        
        if (inStart >= inEnd || postStart >= postEnd) {
            return null;
        }

        int rootVal = postorder[postEnd - 1];
        // int rootIndex = getIndex(inorder, rootVal);
        int rootIndex = map.get(rootVal);
        // 左子树长度
        int leftLength = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        // 拆分左子树，包前不包后
        root.left = split(inorder, inStart, rootIndex, postorder, postStart, postStart + leftLength);
        // 拆分右子树，同上
        root.right = split(inorder, rootIndex + 1, inEnd, postorder, postStart + leftLength, postEnd - 1);
        return root;
    }

    /*private int getIndex(int[] order, int val) {
        int index = 0;
        for (int i = 0; i < order.length; ++i) {
            if (order[i] == val) {
                index = i;
                break;
            }
        }
        return index;
    }*/

}