树、BST 与 Trie · HTML
数学 / 逻辑形态
严格 BST：左子树所有值 < node.val < 右子树所有值。验证可递归传 (low,high)，或中序要求 prev < current；搜索每次按比较排除一整棵子树。重复值策略必须显式定义。
识别信号
- 结构明确是 binary search tree。
- 问题涉及验证、查找、第 k 小、前驱/后继或区间剪枝。
- 中序次序与值排序相同。
- 比较目标值后可排除左/右整棵子树。
- 祖先上下界比只比较父子更重要。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 普通二叉树 | 没有全局排序时不能按值剪枝，中序也不保证有序。 |
| 只检查 node 与直接孩子 | 远端后代可能违反祖先界限而仍满足局部父子比较。 |
| 树可能含重复值但规则未知 | 严格/左含等/右含等会改变 bounds 与中序比较，必须先确认。 |
核心不变量
递归到 node 时，(low,high) 是所有祖先约束的交集；合法节点值必须位于其中，中序遍历的已访问前缀严格有序。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前节点与祖先上下界，或迭代中序栈、prev 和访问秩。 |
| Transition | 验证时左传 (low,node.val)，右传 (node.val,high)；秩查询中序 pop 时计数。 |
| Frontier / order | 搜索沿一条根到叶路径；中序用栈保存尚未访问的祖先与其右子树。 |
Python 骨架
def is_valid_bst(root):
stack, node = [], root
prev = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if prev is not None and node.val <= prev:
return False
prev = node.val
node = node.right
return True
正确性思路
- BST 定义蕴含中序先访问全部较小值，再节点，再全部较大值，故合法树中序严格递增。
- 若中序严格递增，对任一节点，左子树中序片段全在节点之前且更小，右片段全在之后且更大，递归满足全局 BST 条件。
- 模板恰按中序比较每一对相邻值，因此验证等价条件。
复杂度
| Time | Space | Parameters |
|---|
| 验证/全中序 O(n)；平衡 BST 搜索 O(h)=O(log n)，最坏 O(n) | O(h) 栈 | n 为节点数，h 为树高。 |
边界条件
- 空树
- 重复值策略
- 极值不要用有限 sentinel
- prev=0 与负值
- 退化树深度
- 第 k 小的 k 越界
错误模式
| Pattern | Why it fails / fix |
|---|
| 只比较直接孩子 | 无法捕捉右子树中小于远祖先的节点；需祖先 bounds 或全局中序。 |
| 用 32 位极值作无限界 | 节点可能等于 sentinel；使用 None 或数学无穷。 |
| prev 用假值判断 | prev=0 合法，必须检查 prev is not None。 |
| 误以为 BST 必平衡 | 搜索复杂度是 O(h)，退化时 O(n)。 |
选择与排除规则
- 先确认是否真是 BST 与重复值政策。
- 验证用祖先 bounds 或中序 prev，不用局部孩子比较。
- 秩/有序输出优先中序。
- 单值查找利用比较沿一条路径剪枝。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | bounds 或中序 [3,9,8] 都能识别无效。 |
| Setup | 根 8，左子 3；节点 3 的右子为 9。 |
| Trace | 9>3 满足局部父子比较，但它位于根 8 的左子树，违反上界 8。 |
Recall prompts
我的补充