【LeetCode】根据前序和后序遍历构造二叉树

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

题目：

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。如果存在多个答案，您可以返回其中 任何 一个。

题解：

• 递归逻辑和 (根据前序和中序、根据后序和中序)的逻辑基本一致；
• 注意：当preStart == preEnd时需直接返回当前节点，如果不单独进行处理可能会导致接下来的语句越界。

class Solution {
        int[] preorder, postorder;
        Map<Integer, Integer> map = new HashMap<>();
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        this.preorder = preorder;
        this.postorder = postorder;
        for (int i = 0; i < postorder.length; i++)
            map.put(postorder[i], i);
        return build(0, preorder.length - 1, 0, postorder.length - 1);
    }

    TreeNode build(int preStart, int preEnd, int postStart, int postEnd){
        //若判断语句改为(preStart > preEnd || postStart > postEnd)
        //会产生冗余，因为 postEnd - postStart == preEnd - preStart
        if (preStart > preEnd) {
            return null;
        }
        //一定要特别处理
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        Integer index = map.get(preorder[preStart + 1]);
        root.left = build(preStart + 1, index - postStart + preStart + 1, postStart, index);
        root.right = build(index - postStart + preStart + 2, preEnd, index + 1, postEnd - 1);
        return root;
    }
}