LeetCode 889. 从前序与后序遍历序列构造二叉树

2024-09-12 HGNULB 约 6 分钟

文章信息 9 个分类 6 个标签

分类

题目描述

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

题意分析

给出同一棵二叉树的前序遍历和后序遍历两个数组，要求还原出这棵树并返回根节点。题目明确说明：如果存在多棵满足条件的树，返回其中任意一棵即可。

「任意一棵」这四个字是本题与 105、106 最本质的差别，也是必须先想明白的地方。前序的形状是 [根][左子树][右子树]，后序的形状是 [左子树][右子树][根]。当某个节点同时拥有左右孩子时，前序里紧跟着根的那个元素一定是左子树的根，后序里紧挨着根之前的那个元素一定是右子树的根，两个序列联手就能把左右子树切开。但当某个节点只有一个孩子时，无论这个孩子挂在左边还是右边，产生的前序和后序完全一样，信息在这里天然丢失了——这就是答案不唯一的根源，而不是题目出得不严谨。

约束方面：节点数最多 30，值互不相同且都在 1 到 30 之间。「值互不相同」是能靠值反查位置的前提，一旦允许重复，按值定位就会串到别的子树上去。「最多 30 个节点」说明数据规模极小，$O(n^2)$ 甚至更差的写法都能通过，但这恰恰意味着面试官考的不是能不能过，而是能不能讲清楚切分的依据和不唯一的原因。

边界有两个：当前处理的区间为空，此时返回空；当前区间只剩一个节点，此时它是一片叶子，绝不能再去读「根后面的那个元素」，因为那个位置已经属于兄弟子树了。

解法：递归切分遍历区间

核心思路

前序遍历是 [根][左子树][右子树]，后序遍历是 [左子树][右子树][根]。当前子树的根可由前序首元素确定；若子树不止一个节点，就把 preorder[preLeft + 1] 视为左子树根，在后序中找到它的位置，便能得到左子树大小。

这里要先说明答案为何不唯一：若某个节点只有一个孩子，把它放在左边或右边，前序和后序都不变。本解法统一把这个孩子放到左侧，题目允许返回任意合法树。

递归状态使用 build(preLeft, postLeft, size)，表示两个遍历数组从各自起点开始的 size 个元素描述同一棵子树。设左子树大小为 leftSize，则：

左子树：前序起点 preLeft + 1，后序起点 postLeft，长度 leftSize；

右子树：前序起点 preLeft + 1 + leftSize，后序起点 postLeft + leftSize，长度 size - 1 - leftSize。

用哈希表记录后序遍历的“节点值到下标”，每次切分只需 $O(1)$ 查询。节点值互不相同，是按值定位能够成立的前提。

解题步骤

扫描 postorder，建立节点值到下标的映射。

若当前 size == 0，返回空节点；否则以前序首元素创建根节点。

若 size == 1，当前节点是叶子，直接返回，避免访问不存在的 preLeft + 1。

将前序中的下一个节点视为左子树根，在后序中找到它；闭区间长度为 leftRootIndex - postLeft + 1。

按左右子树的起点和长度递归构造，再返回根节点。

例如 preorder = [1,2,4,5,3]、postorder = [4,5,2,3,1]：节点 1 的左子树根是 2，它在后序下标 2，所以左子树有 3 个节点，左右子树自然切成 [2,4,5] 与 [3]。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int[] preorder;
    private Map<Integer, Integer> postIndex;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        this.preorder = preorder;
        postIndex = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postIndex.put(postorder[i], i);
        }
        return build(0, 0, preorder.length);
    }

    private TreeNode build(int preLeft, int postLeft, int size) {
        if (size == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preLeft]);
        if (size == 1) {
            return root;
        }

        int leftRootIndex = postIndex.get(preorder[preLeft + 1]);
        int leftSize = leftRootIndex - postLeft + 1;
        root.left = build(preLeft + 1, postLeft, leftSize);
        root.right = build(
                preLeft + 1 + leftSize,
                postLeft + leftSize,
                size - 1 - leftSize
        );
        return root;
    }
}

func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
    postIndex := make(map[int]int, len(postorder))
    for i, value := range postorder {
        postIndex[value] = i
    }

    var build func(preLeft, postLeft, size int) *TreeNode
    build = func(preLeft, postLeft, size int) *TreeNode {
        if size == 0 {
            return nil
        }

        root := &TreeNode{Val: preorder[preLeft]}
        if size == 1 {
            return root
        }

        leftRootIndex := postIndex[preorder[preLeft+1]]
        leftSize := leftRootIndex - postLeft + 1
        root.Left = build(preLeft+1, postLeft, leftSize)
        root.Right = build(
            preLeft+1+leftSize,
            postLeft+leftSize,
            size-1-leftSize,
        )
        return root
    }

    return build(0, 0, len(preorder))
}

复杂度分析

时间复杂度：$O(n)$。建表与构造各扫描所有节点一次。

空间复杂度：$O(n)$。索引表占 $O(n)$；递归栈为 $O(h)$，最坏树高 $h=n$。返回的树不计入额外空间。

关键点总结

前序确定根，后序中“左子树根的位置”确定左子树长度。

用“起点 + 长度”表示子树，可直接保证前序区间与后序区间等长。

只有一个孩子时无法判断左右归属；统一构造成左孩子即可。

size == 1 必须提前返回，否则会越界读取下一节点。

易错点总结

把后序末元素当作左子树根：它其实是当前根。

leftSize 忘记加 1：后序切片是闭区间，会少算一个节点。

右子树长度仍写成 size - leftSize：没有扣掉当前根。

认为前序加后序总能唯一还原二叉树：单孩子节点就是反例。

每层在线性扫描后序找位置：正确但最坏会退化到 $O(n^2)$。

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	中序直接给出左右分界，答案唯一，不存在单孩子歧义
106. 从中序与后序遍历序列构造二叉树	中等	根取自后序末位，切分方向从右往左，同样答案唯一
1008. 前序遍历构造二叉搜索树	中等	只给一个序列，靠搜索树的值域上下界代替第二个序列来定分界
654. 最大二叉树	中等	分界点由「区间最大值位置」决定，可用单调栈做到线性
108. 将有序数组转换为二叉搜索树	简单	分界点自己选取中点即可，目标是平衡而非还原某棵特定的树
109. 有序链表转换二叉搜索树	中等	同上但只能顺序访问，要用快慢指针找中点或改成中序模拟构建
297. 二叉树的序列化与反序列化	困难	反过来设计序列，用空节点占位补齐信息，从而做到还原唯一
剑指 Offer 07. 重建二叉树	中等	与 105 同题，可直接套用
面试题 04.02. 最小高度树	简单	与 108 同题，可直接套用