一、题目大意

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

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

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]

输出: [1]

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

先序遍历顺序是根左右，后序遍历顺序是 左右根，要建立树，肯定要从根节点开始创建，然后再创建左右子节点，根据先序和后序的特点，根节点的位置是固定的，即是先序遍历的第一个，又是后序遍历的最后一个，知道了根节点位置，我们需要分隔左右子树的区间。

先序遍历：[1][2,4,5][3,6,7]

后序遍历：[4,5,2][6,7,3][1]

先序和后序中各自左子树区间长度相等，数字顺序可能不同，通过观察2和3分别是左子树和右子树的根节点（先序的头后序的尾），可以根据其来定位左右子树区间的位置范围了，拆分数组，可以用双指针来指向子区间的开头和末尾。用preL和preR分别代表左子树区间的开头和结尾位置，postL和postR表示右子树区间的开头和结尾位置，那么若preL大于preR或者postL大于postR的时候，说明已经不存在子树区间，直接返回空指针。然后要先新建当前树的根节点，就通过pre[preL]取到即可，接下来要找左子树的根节点在post中的益，最简单的方法就是遍历post中的区间[postL, postR]，找到其位置idx，然后根据这个idx就可以算出左子树区间长度为len = (idx - postL) + 1，那么pre数组中左子树区间为[preL+1, preL+len]，右子树区间为[preL+1+len, preR]，同理，post数组中左子树区间为[postL, idx]，右子树区间为[idx+1, postR-1]。知道了这些信息，就可以调用递归函数了。

三、解题方法

3.1 Java实现

public class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return helper(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }

    TreeNode helper(int[] pre, int preL, int preR, int[] post, int postL, int postR) {
        if (preL > preR || postL > postR) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preL]);
        if (preL == preR) {
            return node;
        }
        int idx = -1;
        for (idx = postL; idx <= postR; idx++) {
            if (pre[preL + 1] == post[idx]) {
                break;
            }
        }
        node.left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
        node.right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
        return node;
    }
}

四、总结小记

• 2022/10/6 今天今天有点冷