LeetCode 889.根据前序和后序遍历构造二叉树

题目：

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

思路：题目说，如果存在多个答案，我们可以返回其中任何一个。那么不妨规定：无论什么情况，在前序遍历中，preorder[1] 都是左子树的根节点值。

递归边界：

• 如果 preorder 的长度是 0，对应着空节点，返回空。
• 如果 preorder 的长度是 1，对应着二叉树的叶子，创建一个叶子节点并返回。

代码：

/**
 * 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 {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int n = postorder.length;
        Map<Integer, Integer> index = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            index.put(postorder[i], i);
        }
        return dfs(preorder, 0, n, 0, n, index);
    }

    private TreeNode dfs(int[] preorder, int preL, int preR, int posL, int posR, Map<Integer, Integer> index) {
        if (preL == preR)
            return null;
        if (preL + 1 == preR)
            return new TreeNode(preorder[preL]);
        int leftSize = index.get(preorder[preL + 1]) - posL + 1;
        TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize, posL, posL + leftSize, index);
        TreeNode right = dfs(preorder, preL + 1 + leftSize, preR, posL + leftSize, posR - 1, index);
        return new TreeNode(preorder[preL], left, right);
    }
}

性能：