二叉搜索树
BST 是面试中最常见的数据结构。关键不是会写 CRUD，而是理解为什么 BST 查找是 O(log n)，以及BST 和平衡树的区别。
面试考察点
面试官通过这道题想考察：
1. 你是否理解 BST 的定义和性质
2. 你是否能解释为什么 BST 中序遍历有序
3. 你是否能验证 BST（易错题！）
4. 你是否理解 BST 和平衡 BST 的区别
一、BST 的定义和性质
1.1 什么是 BST？（小白解释）
面试官追问："什么是 BST？"
BST = 二叉搜索树
定义：
对于每个节点：
- 左子树所有节点 < 该节点
- 右子树所有节点 > 该节点
- 左右子树也是 BST
示例：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
验证：
- 根节点 8：左子树 [1,3,6,4,7] < 8，右子树 [10,14,13] > 8 ✓
- 节点 3：左子树 [1] < 3，右子树 [6,4,7] > 3 ✓
- ...
面试回答：简单说就是"左小右大"的二叉树
1.2 为什么 BST 查找是 O(log n)？
面试官追问："BST 查找为什么是 O(log n)？"
查找过程：
查找 6：
8
/ \
3 10 8 > 6，去左子树
/ \
1 6 3 < 6，去右子树
/ \
4 7 找到 6！
查找 5：
8
/ \
3 10 8 > 5，去左子树
/ \
1 6 3 < 6，去右子树
/ \
4 7 6 > 5，去左子树
/
(null) 没找到
关键洞察：
每次比较都能排除一半的可能性！
有 n 个节点的平衡 BST：
- 树高 ≈ log₂(n)
- 最多比较 log₂(n) 次
- 所以是 O(log n)！
1.3 BST 的问题：退化
面试官追问："BST 查找真的是 O(log n) 吗？"
注意！BST 查找是 O(log n) 的前提是：树是平衡的！
如果数据有序插入呢？
插入 1, 2, 3, 4, 5：
1
\
2
\
3
\
4
\
5
树退化成链表！
查找变成 O(n)！
这就是为什么需要平衡树（如 AVL、红黑树）！
它们通过旋转保持平衡，保证 O(log n)。
二、BST 的核心性质
2.1 中序遍历 BST 得到有序序列（面试必问）
面试官追问："BST 中序遍历为什么是有序的？"
BST 的中序遍历（ 左 → 根 → 右）：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
中序遍历过程：
1. 先遍历左子树 [1, 3, 4, 6, 7]
2. 处理根 8
3. 再遍历右子树 [10, 13, 14]
结果：1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14
为什么有序？
因为 BST 的定义是"左 < 根 < 右"
中序遍历先访问所有左子树（更小的）
再访问根，最后访问右子树（更大的）
面试加分点：
"BST 中序有序这个性质很有用，
可以 O(log n) 找第 K 小/第 K 大元素"
2.2 验证 BST（易错题！）
面试官追问："怎么验证一个二叉树是 BST？"
错误解法：
def isBST(root):
if not root:
return True
if root.left and root.left.val > root.val:
return False
if root.right and root.right.val < root.val:
return False
return isBST(root.left) and isBST(root.right)
反例：
5
/ \
3 7
/ \
6 8
这个解法会返回 True（每个节点都满足左<根<右）
但实际上不是 BST！因为 6 在 5 的右子树里，但 6 < 5 是错的！
正确解法：带上下界
def isBST(root):
def validate(node, min_val, max_val):
if not node:
return True
# 当前节点必须在 (min_val, max_val) 范围内
if node.val <= min_val or node.val >= max_val:
return False
# 左子树的上界是当前节点
# 右子树的下界是当前节点
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
面试加分点：
"这道题的错误率很高，
关键是理解 BST 的约束是全局的，不是局部的"
三、面试总结
BST 核心要点
┌─────────────────────────────────────────────────┐
│ BST 核心 │
├─────────────────────────────────────────────────┤
│ │
│ 定义：左 < 根 < 右 │
│ │
│ 性质： │
│ - 查找 O(log n)（平衡时） │
│ - 中序遍历有序 │
│ │
│ 坑： │
│ - 有序插入会退化成链表 │
│ - 验证 BST 要带上下界，不是只看局部 │
│ │
│ 延伸： │
│ - 平衡 BST（AVL、红黑树） │
│ - B 树（数据库索引） │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释为什么是 O(log n)
"每次比较排除一半，树高是 log n"
2. 能解释中序遍历有序
"BST 定义是左<根<右，中序遍历就是从小到大"
3. 能避免验证 BST 的错误
"验证 BST 不能只看局部，要带全局上下界"
相关题目
- LeetCode 98 - 验证二叉搜索树 - BST 验证
- LeetCode 230 - 二叉搜索树中第K小的元素 - BST 性质应用