LeetCode 题解工作台
前序遍历构造二叉搜索树
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先 序遍历 ，构造树并返回其根。 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。 二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 $\textit{dfs}(i, j)$，表示构造出从 到 这些节点构成的二叉搜索树。那么答案就是 $\textit{dfs}(0, n - 1)$。 在 $\textit{dfs}(i, j)$ 中，我们首先构造根节点，即 。然后使用二分查找的方法找到第一个大于 的节点的下标 ，将 $\textit{dfs}(i + 1, \textit{mid} - 1)$ 作为根节点…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
示例 1：
输入：preorder = [8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
示例 2:
输入: preorder = [1,3] 输出: [1,null,3]
提示：
1 <= preorder.length <= 1001 <= preorder[i] <= 10^8preorder中的值 互不相同
解题思路
方法一：DFS + 二分查找
我们设计一个函数 ，表示构造出从 到 这些节点构成的二叉搜索树。那么答案就是 。
在 中，我们首先构造根节点，即 。然后使用二分查找的方法找到第一个大于 的节点的下标 ，将 作为根节点的左子树，将 作为根节点的右子树。
最后返回根节点即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
def dfs(i: int, j: int) -> Optional[TreeNode]:
if i > j:
return None
root = TreeNode(preorder[i])
l, r = i + 1, j + 1
while l < r:
mid = (l + r) >> 1
if preorder[mid] > preorder[i]:
r = mid
else:
l = mid + 1
root.left = dfs(i + 1, l - 1)
root.right = dfs(l, j)
return root
return dfs(0, len(preorder) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n) for iterative or optimized recursive approaches to potentially O(n^2) if naive insertion is used. Space complexity is O(h) for recursion or stack, where h is the height of the BST, up to O(n) in the worst case. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Watch for correct placement of nodes respecting BST property for left and right subtrees.
- question_mark
Expect candidates to optimize recursive calls or avoid unnecessary stack growth.
- question_mark
Check handling of edge cases with minimal or maximal preorder values.
常见陷阱
外企场景- error
Inserting nodes without validating BST bounds can violate tree structure.
- error
Mismanaging stack updates can lead to incorrect parent-child assignments.
- error
Assuming preorder order directly maps to left-right placement without bound checks.
进阶变体
外企场景- arrow_right_alt
Construct BST from postorder traversal instead of preorder, reversing insertion logic.
- arrow_right_alt
Rebuild a BST given both inorder and preorder arrays for precise reconstruction.
- arrow_right_alt
Determine the height of the BST while constructing it from preorder traversal.