#yyds干货盘点# LeetCode程序员面试金典：从中序与后序遍历序列构造二叉树

题目：

给定两个整数数组 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]

代码实现：

class Solution {    int post_idx;    int[] postorder;    int[] inorder;    Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();    public TreeNode helper(int in_left, int in_right) {        // 假如这里没有节点来构造二叉树，就结束        if (in_left > in_right) {            return null;        }        // 选择 post_idx 作为当前子树根节点的位置元素        int root_val = postorder[post_idx];        TreeNode root = new TreeNode(root_val);        // 根据 root 位置分为左右两棵子树        int index = idx_map.get(root_val);        // 下标减一        post_idx--;        // 构造右子树        root.right = helper(index + 1, in_right);        // 构造左子树        root.left = helper(in_left, index - 1);        return root;    }    public TreeNode buildTree(int[] inorder, int[] postorder) {        this.postorder = postorder;        this.inorder = inorder;        // 从后序遍历的最后一个元素开始        post_idx = postorder.length - 1;        // 建立(元素，下标)哈希表键值对        int idx = 0;        for (Integer val : inorder) {            idx_map.put(val, idx++);        }                return helper(0, inorder.length - 1);    }}