根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3
/ \
9 20
/ \
15 7

解题思路

方法一：递归

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    // 建立哈希表，用于查询当前结点的下标
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0){
            return null;
        }
        for(int i = 0; i < inorder.length; ++i){
            map.put(inorder[i], i);
        }
        TreeNode head = new TreeNode();
        // 递归建立二叉树
        build(inorder, postorder, 0, inorder.length-1, postorder.length - 1, head);
        return head;
    }
    // left、right为当前子树的在中心遍历数组中的左右边界
    // pos为当前后序遍历的下标，也就是当前子树的头结点
    // head为头结点
    private void build(int[] inorder, int[] postorder, int left, int right, int pos, TreeNode head){
        // 给头结点赋值
        head.val = postorder[pos];
        // 获取当前头结点在中序遍历数组中的下标
        int index = map.get(postorder[pos]);
        // 递归创建右子树
        // 如果当前头结点的右边有结点
        if(right > index){
            // 创建右边子头结点
            TreeNode rightNode = new TreeNode();
            // 头结点相连
            head.right = rightNode;
            // 递归  后序遍历数组下标为当前下标减一
            build(inorder, postorder, index + 1, right, pos - 1, rightNode);
        }
        // 递归创建左子树
        if(index > left){
            TreeNode leftNode = new TreeNode();
            head.left = leftNode;
            // // 递归  后序遍历数组下标为当前下标减一再减去右子树的结点长度
            build(inorder, postorder, left, index - 1, pos - 1 - right + index, leftNode);
        }
    }
}

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    Map<Integer, Integer> inMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; ++i){
            inMap.put(inorder[i], i);
        }
        return recur(postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    // inLeft, inRight中序范围
    // postLeft, postRight 后续范围
    private TreeNode recur(int[] postorder, int inLeft, int inRight, int postLeft, int postRight){
        // 中序中不存在结点
        if(inLeft > inRight){
            return null;
        }
        // 获取当前结点，即后续遍历最后一个结点
        int val = postorder[postRight];
        // 创建根节点
        TreeNode root = new TreeNode(val);
        // 获取当前结点在中序遍历中的位置
        int pos = inMap.get(val);
        // 遍历左节点
        root.left = recur(postorder, inLeft, pos - 1, postLeft, postLeft + pos - inLeft - 1);
        // 遍历右节点, 后续遍历最后一个结点已经遍历过，缩小范围
        // 中续遍历一个结点已经遍历过，缩小范围
        root.right = recur(postorder, pos + 1, inRight, postLeft + pos - inLeft, postRight - 1);
        return root;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)