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

题目

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

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

示例

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

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

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

方法1：递归

• 使用哈希表存储postorder中值与索引的对应关系。
• 把前序遍历结果的第一个元素确定为根节点的值。
• 把前序遍历结果的第二个元素作为左子树的根节点的值。
• 在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。

Java实现

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

    public TreeNode construct(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        if (preStart == preEnd) return new TreeNode(preorder[preStart]);

        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        int leftSize = map.get(leftRootVal) - postStart + 1;
        TreeNode root = new TreeNode(rootVal);
        root.left = construct(preorder, preStart + 1, preStart + leftSize, postorder, postStart, postStart + leftSize - 1);
        root.right = construct(preorder, preStart + leftSize + 1, preEnd, postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23