当前位置：首页 > news >正文

面试经典150题[072]：从前序与中序遍历序列构造二叉树（LeetCode 105）

news 2026/8/2 19:50:22

从前序与中序遍历序列构造二叉树（LeetCode 105）

题目链接：从前序与中序遍历序列构造二叉树（LeetCode 105）
难度：中等

1. 题目描述

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

要求：

树中不存在重复元素
数组长度 1 <= n <= 3000
-3000 <= preorder[i], inorder[i] <= 3000

示例：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]

输入: preorder = [-1], inorder = [-1] 输出: [-1]

2. 问题分析

2.1 规律

先序遍历：根节点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根节点 -> 右子树
先序的第一个元素总是根节点，在中序中找到根节点的位置，可以分割左/右子树。
递归构建：左子树的前序/中序子序列，右子树的前序/中序子序列。
核心问题：如何高效找到中序中根节点的位置，以分割子树？

2.2 贪心思路

我们使用递归 + 哈希表优化：

使用哈希表存储中序遍历的值到索引的映射，便于 O(1) 查找根节点位置。
递归函数：参数为前序/中序的起始/结束索引。
步骤：
- 如果子树为空（start > end），返回 None。
- 取前序第一个元素作为根，pre_idx += 1。
- 在中序中找到根索引 root_in_idx。
- 递归构建左子树：中序 [in_start, root_in_idx-1]，前序相应部分。
- 递归构建右子树：中序 [root_in_idx+1, in_end]，前序相应部分。
全局 pre_idx 跟踪前序位置，避免切片开销。

3. 代码实现

Python

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defbuildTree(self,preorder:List[int],inorder:List[int])->Optional[TreeNode]:defhelper(in_start,in_end):nonlocalpre_idxifin_start>in_end:returnNoneroot_val=preorder[pre_idx]root=TreeNode(root_val)pre_idx+=1root_in_idx=idx_map[root_val]root.left=helper(in_start,root_in_idx-1)root.right=helper(root_in_idx+1,in_end)returnroot n=len(preorder)idx_map={val:ifori,valinenumerate(inorder)}pre_idx=0returnhelper(0,n-1)

C++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:TreeNode*buildTree(vector<int>&preorder,vector<int>&inorder){unordered_map<int,int>idx_map;for(inti=0;i<inorder.size();++i){idx_map[inorder[i]]=i;}intpre_idx=0;returnhelper(preorder,inorder,idx_map,pre_idx,0,inorder.size()-1);}private:TreeNode*helper(vector<int>&preorder,vector<int>&inorder,unordered_map<int,int>&idx_map,int&pre_idx,intin_start,intin_end){if(in_start>in_end){returnnullptr;}introot_val=preorder[pre_idx];TreeNode*root=newTreeNode(root_val);++pre_idx;introot_in_idx=idx_map[root_val];root->left=helper(preorder,inorder,idx_map,pre_idx,in_start,root_in_idx-1);root->right=helper(preorder,inorder,idx_map,pre_idx,root_in_idx+1,in_end);returnroot;}};