从中序与后序遍历序列构造二叉树 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请构造二叉树并返回其根节点。

题目保证两数组长度相等、元素无重复，且确实对应一棵二叉树的中序与后序序列；长度在 [1, 3000] 内。

示例 1

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出：[3,9,20,null,null,15,7]

后序末元素 3 为根；中序里 3 左侧 [9] 为左子树、右侧 [15,20,7] 为右子树；从后序右端向左「消费」节点时须先建右子树再左子树。

示例 2

输入：inorder = [-1], postorder = [-1]

输出：[-1]

💭 模拟答题者思考

1. 暴力直觉：枚举所有二叉树形状再验证中序、后序是否匹配——指数级，不可行。

2. 后序的最后一个数一定是当前子树的根；中序里根左边是左子树的中序、右边是右子树的中序——子问题同型，可分治。

3. 与 #105 先序版对比：先序从前往后取根，递归「先左后右」；后序从后往前取根，后序数组里同一子树的节点是「左段 + 右段 + 根」，从右端消费时必须先处理右子树再左子树，否则 post_i 错位。

4. 用 idx_map O(1) 找根在中序的位置，配合全局 post_i，每个节点只建一次 → O(n)。

5. 示例 1：根 3（post 末），中序 mid=1；先建右子树 inorder[15,20,7]，根 20，再 7、15；再建左子树 9。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`postorder[post_i]`	int / 游标	定义：全局后序指针，从数组末尾向前，下一个要「落地」为树节点的值（当前子树的根）维护：每创建一个节点后 `post_i -= 1`，顺序与后序从右向左扫一致更新：递归须先右后左，才能与后序中「左子树段 → 右子树段 → 根」的布局对齐
`in_left, in_right`	int	定义：当前子树在 `inorder` 中的闭区间下标维护：`in_left > in_right` 表示空子树，返回 `null` 更新：根在中序位置 `mid` 处，左子树 `[in_left, mid-1]`，右子树 `[mid+1, in_right]`
`idx_map[val]`	哈希表	定义：中序每个值 → 下标，O(1) 找根在中序中的位置维护：构造前一次性建好，全程不变更新：读到根值 `root_val` 后 `mid = idx_map[root_val]` 用于切分左右区间
`root`	TreeNode*	定义：当前子树的根，值来自当前 `postorder[post_i]` 维护：先挂好 `right`、`left` 再返回给上层（与先序题「先左后右」相反）更新：`root.right = dfs(...)` 再 `root.left = dfs(...)`

⌨️ 落码步骤

1. 建 idx_map：inorder[i] → i

2. post_i = len(postorder) - 1，定义 dfs(in_left, in_right)：若 in_left > in_right 返回 null

3. 取 root_val = postorder[post_i]，post_i -= 1，mid = idx_map[root_val]，新建根节点

4. 先 root.right = dfs(mid + 1, in_right)，再 root.left = dfs(in_left, mid - 1)

5. 从 dfs(0, len(inorder)-1) 返回整棵树的根

💻 代码实现

class Solution:
    def buildTree(self, inorder: list[int], postorder: list[int]) -> TreeNode | None:
        idx_map = {v: i for i, v in enumerate(inorder)}
        post_i = len(postorder) - 1

        def dfs(in_left: int, in_right: int) -> TreeNode | None:
            nonlocal post_i
            if in_left > in_right:
                return None
            root_val = postorder[post_i]
            post_i -= 1
            mid = idx_map[root_val]
            node = TreeNode(root_val)
            node.right = dfs(mid + 1, in_right)
            node.left = dfs(in_left, mid - 1)
            return node

        return dfs(0, len(inorder) - 1)

class Solution {
    int post_i = 0;
    unordered_map<int, int> idx_map;

    TreeNode* dfs(int in_left, int in_right, vector<int>& postorder) {
        if (in_left > in_right) return nullptr;
        int root_val = postorder[post_i--];
        int mid = idx_map[root_val];
        auto* root = new TreeNode(root_val);
        root->right = dfs(mid + 1, in_right, postorder);
        root->left = dfs(in_left, mid - 1, postorder);
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        idx_map.clear();
        for (int i = 0; i < (int)inorder.size(); ++i)
            idx_map[inorder[i]] = i;
        post_i = (int)postorder.size() - 1;
        return dfs(0, (int)inorder.size() - 1, postorder);
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)（中序下标哈希表 + 递归栈 O(h)）

⚠️ 常见坑

❗ 照搬先序题「先左后右」：后序从尾向前消费，必须先右后左，否则 post_i 与子树区间不对应。

❗ 根取 postorder[0]：后序根在区间末尾，不是开头。

❗ 右子树中序区间写成 [mid, in_right]：根已在 mid，右子树必须从 mid + 1 开始。

🔍 必测边界 Case

Case 1：单节点

inorder = [-1], postorder = [-1] → 根 -1，无孩子

Case 2：只有左链

in = [3,2,1], post = [3,2,1] → 每层只有左孩子，后序与左链逆序一致

Case 3：只有右链

in = [1,2,3], post = [1,2,3] → 每层只有右孩子

Case 4：官方示例 1

inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

Case 5：右子树为空

根在中序最右端 → dfs(mid+1, in_right) 立即返回 null，再建左子树