LeetCode 106. 从中序与后序遍历序列构造二叉树

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归分治 + 哈希索引（推荐）
相似题目

题目描述

✅ 106. 从中序与后序遍历序列构造二叉树

思路分析

解法一：递归分治 + 哈希索引（推荐）

核心思路：

后序遍历的最后一个元素是当前子树根结点。

在中序遍历中找到根的位置，即可确定左、右子树区间。

用哈希表记录中序下标，递归构建左右子树。

复杂度分析：

时间复杂度：O(n)，其中 n 为结点数量。

空间复杂度：O(n)，哈希表与递归栈占用。

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

    private TreeNode build(int inL, int inR, int postL, int postR,
                           int[] inorder, int[] postorder, Map<Integer, Integer> indexMap) {
        if (inL > inR) {
            return null;
        }

        int rootVal = postorder[postR];
        int k = indexMap.get(rootVal);
        int leftSize = k - inL;

        // 按中序分割区间递归构建左右子树
        TreeNode root = new TreeNode(rootVal);
        root.left = build(inL, k - 1, postL, postL + leftSize - 1, inorder, postorder, indexMap);
        root.right = build(k + 1, inR, postL + leftSize, postR - 1, inorder, postorder, indexMap);
        return root;
    }
}

func buildTree(inorder []int, postorder []int) *TreeNode {
    indexMap := make(map[int]int, len(inorder))
    for i, v := range inorder {
        indexMap[v] = i
    }

    var build func(inL, inR, postL, postR int) *TreeNode
    build = func(inL, inR, postL, postR int) *TreeNode {
        if inL > inR {
            return nil
        }

        rootVal := postorder[postR]
        k := indexMap[rootVal]
        leftSize := k - inL

        // 按中序分割区间递归构建左右子树
        root := &TreeNode{Val: rootVal}
        root.Left = build(inL, k-1, postL, postL+leftSize-1, inorder, postorder)
        root.Right = build(k+1, inR, postL+leftSize, postR-1, inorder, postorder)
        return root
    }

    return build(0, len(inorder)-1, 0, len(postorder)-1)
}

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	分治
889. 根据前序和后序遍历构造二叉树	中等	分治
102. 二叉树的层序遍历	中等	BFS
94. 二叉树的中序遍历	简单	递归/栈
145. 二叉树的后序遍历	简单	递归/栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/66276999