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

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
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int tmp : postorder) {
            stack.push(tmp);
        }
        for (int i = 0; i < inorder.length; i++) {
            arrayList.add(inorder[i]);
            hashMap.put(inorder[i], i);
        }
        TreeNode root = process(stack, arrayList, hashMap, 0, postorder.length - 1);
        return root;
    }

    public TreeNode process(Stack<Integer> postorder, ArrayList<Integer> inorder,
                            HashMap<Integer, Integer> nodeIndexs, int start, int end) {
        if (start > end || postorder.isEmpty()) {
            return null;
        }
        if (start == end) {
            return new TreeNode(postorder.pop());
        }
        int val = postorder.pop();
        TreeNode root = new TreeNode(val);
        int index = nodeIndexs.get(val);
        TreeNode right = process(postorder, inorder, nodeIndexs, index + 1, end);
        TreeNode left = process(postorder, inorder, nodeIndexs, start, index - 1);
        root.left = left;
        root.right = right;
        return root;
    }
}