[数据结构与算法]LeetCode 106. 从中序与后序遍历序列构造二叉树

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

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

例如，给出

中序遍历 inorder =?[9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
?

/**
 * 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;
    int[] post;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        //假设元素不重复
        inMap = new HashMap<>();
        for (int i = 0; i < n; i++) inMap.put(inorder[i], i);
        post = postorder;
        return build(0, n-1, 0, n-1);
    }

    public TreeNode build(int inStart, int inEnd, int postStart, int postEnd) {
        //终止条件
        if (inStart > inEnd || postEnd > postEnd) return null;
        //获取根节点元素，中序遍历下根结点index，左子树长度
        TreeNode root = new TreeNode(post[postEnd]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;
        //构造左子树，右子树
        root.left = build(inStart, inRoot -1, postStart, postStart + numsLeft - 1);
        root.right = build(inRoot + 1, inEnd, postStart + numsLeft, postEnd -1);
        return root;
    }
}