题目描述
思路解析动画文字版
记住「取首元素当根;下一个值 ≤ bound 就往当前子树挂、> bound 就回退给祖先;左子树上界收成根值、右子树上界沿用父界」,下面逐帧套它。
看值 · 根：轮到根,上界是 +∞。下一个待读值 10 满足 10 ≤ +∞,说明它属于这棵子树,就在这儿建节点 10。
建 10 · 根：建好节点 10(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 10(左子树都要比 10 小),右孩子的上界沿用父亲传来的 +∞。
看值 · 节点 10 的左孩子：轮到节点 10 的左孩子,上界是 10。下一个待读值 5 满足 5 ≤ 10,说明它属于这棵子树,就在这儿建节点 5。
建 5 · 节点 10 的左孩子：建好节点 5(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 5(左子树都要比 5 小),右孩子的上界沿用父亲传来的 10。
看值 · 节点 5 的左孩子：轮到节点 5 的左孩子,上界是 5。下一个待读值 3 满足 3 ≤ 5,说明它属于这棵子树,就在这儿建节点 3。
建 3 · 节点 5 的左孩子：建好节点 3(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 3(左子树都要比 3 小),右孩子的上界沿用父亲传来的 5。
空位 · 节点 3 的左孩子：轮到节点 3 的左孩子,它的上界是 3。下一个待读值 7 已经 7 > 3,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
空位 · 节点 3 的右孩子：轮到节点 3 的右孩子,它的上界是 5。下一个待读值 7 已经 7 > 5,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
看值 · 节点 5 的右孩子：轮到节点 5 的右孩子,上界是 10。下一个待读值 7 满足 7 ≤ 10,说明它属于这棵子树,就在这儿建节点 7。
建 7 · 节点 5 的右孩子：建好节点 7(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 7(左子树都要比 7 小),右孩子的上界沿用父亲传来的 10。
空位 · 节点 7 的左孩子：轮到节点 7 的左孩子,它的上界是 7。下一个待读值 15 已经 15 > 7,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
空位 · 节点 7 的右孩子：轮到节点 7 的右孩子,它的上界是 10。下一个待读值 15 已经 15 > 10,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
看值 · 节点 10 的右孩子：轮到节点 10 的右孩子,上界是 +∞。下一个待读值 15 满足 15 ≤ +∞,说明它属于这棵子树,就在这儿建节点 15。
建 15 · 节点 10 的右孩子：建好节点 15(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 15(左子树都要比 15 小),右孩子的上界沿用父亲传来的 +∞。
看值 · 节点 15 的左孩子：轮到节点 15 的左孩子,上界是 15。下一个待读值 12 满足 12 ≤ 15,说明它属于这棵子树,就在这儿建节点 12。
建 12 · 节点 15 的左孩子：建好节点 12(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 12(左子树都要比 12 小),右孩子的上界沿用父亲传来的 15。
空位 · 节点 12 的左孩子：轮到节点 12 的左孩子,它的上界是 12。下一个待读值 18 已经 18 > 12,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
空位 · 节点 12 的右孩子：轮到节点 12 的右孩子,它的上界是 15。下一个待读值 18 已经 18 > 15,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
看值 · 节点 15 的右孩子：轮到节点 15 的右孩子,上界是 +∞。下一个待读值 18 满足 18 ≤ +∞,说明它属于这棵子树,就在这儿建节点 18。
建 18 · 节点 15 的右孩子：建好节点 18(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 18(左子树都要比 18 小),右孩子的上界沿用父亲传来的 +∞。
空位 · 节点 18 的左孩子：轮到节点 18 的左孩子,但前序串已经全部读完、没有值可取了,这个位置判为空,回到上一层。
空位 · 节点 18 的右孩子：轮到节点 18 的右孩子,但前序串已经全部读完、没有值可取了,这个位置判为空,回到上一层。
构造完成：前序串读完,整棵 BST 重建好了:根 10,左 5(挂 3、7)、右 15(挂 12、18)。验证它的中序是 3,5,7,10,12,15,18,严格升序,确实是合法 BST。回头看,每个值只被取用一次、靠一个上界就分到了该去的位置,一遍 O(n) 搞定。
边界:单值即根;递增成右链、递减成左链,上界照样分对。
两个追问:还可用单调栈;BST 有序让单给前序就能重建。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]: i = 0 def build(bound): nonlocal i if i == len(preorder) or preorder[i] > bound: return None root = TreeNode(preorder[i]); i += 1 root.left = build(root.val) root.right = build(bound) return root return build(float('inf'))复杂度
- 时间：O(n)，读取指针 i 只前进、不回退,每个值取用一次;每次上界比较是常数,共 O(n)
- 空间：O(h)，只用递归栈,深度等于树高 h;最坏退化成单边链时 O(n),平衡时 O(log n)
易错点
面试追问把动画讲成自己的话
追问除了上界递归,这题还有别的解法吗?
追问和已知前序、中序建普通二叉树(lc105)有什么区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
将二叉搜索树变平衡
LeetCode 1382 · 中等 · 沿着 BST套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题