知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 前序遍历构造二叉搜索树 ## 题目(LeetCode 1008) 给定一个整数数组 `preorder`,它是某棵二叉搜索树的前序遍历结果,请构造该 BST。 ``` 输入:preorder = [8,5,1,7,10,12] 输出:[8,5,10,1,7,null,12] 8 / \ 5 10 / \ \ 1 7 12 ``` ## 核心思路 BST 的性质:左子树所有值 < 根,右子树所有值 > 根。 前序遍历第一个是根(8),后面的元素中,比 8 小的属于左子树,比 8 大的属于右子树。 ``` preorder = [8, | 5, 1, 7, | 10, 12] ↑ ↑ ↑ 根 <8(左子树) >8(右子树) ``` ### 解法一:递归 + 上下界 用上下界(lower, upper)来确定当前节点是否属于当前子树: ``` 构造根 8,范围 (-∞, +∞) 下一个 5,5 在 (-∞, 8) 内 → 是 8 的左子树 下一个 1,1 在 (-∞, 5) 内 → 是 5 的左子树 下一个 7,7 不在 (-∞, 1) 内 → 回溯 7 在 (5, 8) 内 → 是 5 的右子树 下一个 10,10 不在 (5, 8) 内 → 回溯 10 在 (8, +∞) 内 → 是 8 的右子树 下一个 12,12 在 (10, +∞) 内 → 是 10 的右子树 ``` ## 代码 ```java class Solution { private int idx = 0; public TreeNode bstFromPreorder(int[] preorder) { return build(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode build(int[] preorder, int lower, int upper) { if (idx >= preorder.length) return null; int val = preorder[idx]; // 当前值不在合法范围内,说明不属于当前子树 if (val < lower || val > upper) return null; idx++; TreeNode root = new TreeNode(val); root.left = build(preorder, lower, val); // 左子树范围 (lower, val) root.right = build(preorder, val, upper); // 右子树范围 (val, upper) return root; } } ``` ## 解法二:找分界点(更直观) 在前序数组中找到第一个比根大的元素,左边是左子树,右边是右子树: ```java class Solution { public TreeNode bstFromPreorder(int[] preorder) { return build(preorder, 0, preorder.length - 1); } private TreeNode build(int[] preorder, int lo, int hi) { if (lo > hi) return null; TreeNode root = new TreeNode(preorder[lo]); // 找第一个比 root 大的位置 int splitIdx = lo + 1; while (splitIdx <= hi && preorder[splitIdx] < preorder[lo]) { splitIdx++; } root.left = build(preorder, lo + 1, splitIdx - 1); root.right = build(preorder, splitIdx, hi); return root; } } ``` ## 两种解法对比 | | 解法一(上下界) | 解法二(找分界点) | |--|--------|--------| | 时间复杂度 | O(n) | O(n log n) 平均,O(n²) 最坏 | | 空间复杂度 | O(n) | O(n) | | 特点 | 最优,一次遍历 | 直观,但每层要扫描找分界点 | ## 和 105 题的区别 105 题(前序+中序)需要中序来确定左右子树的范围,因为普通二叉树没有大小关系。而 BST 有"左 < 根 < 右"的性质,所以只需要前序遍历就够了,不需要中序。 ## 复杂度 - 解法一:时间 O(n),空间 O(n) - 解法二:时间 O(n²) 最坏,空间 O(n) --- 上一篇:[05 - 有序链表转换为 BST](./05-sorted-list-to-bst.md) | 下一篇:[07 - 构造树总结](./07-summary.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入