二叉搜索树（Binary Search Tree, BST）
一句话说明
二叉搜索树最值钱的性质不是“它是一棵树”，而是“中序遍历有序”，因此很多题都能转成有序数组上的二分思维。
先把核心性质刻进脑子
对任意节点 root：
- 左子树所有节点值都
< root.Val - 右子树所有节点值都
> root.Val
所以 BST 的很多操作，本质都在做“朝一边缩小搜索范围”。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13这类题为什么像二分查找
普通二叉树里，找一个值可能要把整棵树都走完。
但 BST 不一样：
- 如果目标比当前节点小，只去左边
- 如果目标比当前节点大，只去右边
这和二分查找“每次排掉一半不可能区域”是同一个思路。
Go 节点定义
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}Go 代码：查找
func SearchBST(root *TreeNode, val int) *TreeNode {
for root != nil {
if root.Val == val {
return root
}
if val < root.Val {
root = root.Left
} else {
root = root.Right
}
}
return nil
}Go 代码：插入
插入的本质是先找到“应该挂在哪个空位上”。
func InsertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if val < root.Val {
root.Left = InsertIntoBST(root.Left, val)
} else if val > root.Val {
root.Right = InsertIntoBST(root.Right, val)
}
return root
}Go 代码：删除
BST 删除之所以老让人卡住，是因为要分情况。
先记住三种情况
- 没有子节点：直接删
- 只有一个子节点：让孩子顶上来
- 有两个子节点：用后继或前驱替换，再删那个替身节点
最常用的是“用右子树最小节点，也就是后继节点替换”。
func DeleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if key < root.Val {
root.Left = DeleteNode(root.Left, key)
return root
}
if key > root.Val {
root.Right = DeleteNode(root.Right, key)
return root
}
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
successor := root.Right
for successor.Left != nil {
successor = successor.Left
}
root.Val = successor.Val
root.Right = DeleteNode(root.Right, successor.Val)
return root
}Go 代码：验证 BST
很多人第一反应是“只比较左右孩子”，这是不够的。
真正要维护的是整棵子树的上下界。
func IsValidBST(root *TreeNode) bool {
return validate(root, nil, nil)
}
func validate(node *TreeNode, low, high *int) bool {
if node == nil {
return true
}
if low != nil && node.Val <= *low {
return false
}
if high != nil && node.Val >= *high {
return false
}
return validate(node.Left, low, &node.Val) &&
validate(node.Right, &node.Val, high)
}中序遍历是 BST 的总开关
只要题目涉及下面这些关键词，就应该立刻想到中序遍历：
- 第
k小 - 最小绝对差
- 众数
- 转换成递增结构
因为 BST 的中序遍历结果天然有序。
Go 代码：第 K 小元素
func KthSmallest(root *TreeNode, k int) int {
stack := []*TreeNode{}
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
k--
if k == 0 {
return root.Val
}
root = root.Right
}
return -1
}Go 代码：最近公共祖先
这个题特别能体现 BST 的“二分味道”：
- 两个节点都比根小，就往左
- 两个节点都比根大，就往右
- 一大一小，当前根就是分叉点
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
for root != nil {
if p.Val < root.Val && q.Val < root.Val {
root = root.Left
} else if p.Val > root.Val && q.Val > root.Val {
root = root.Right
} else {
return root
}
}
return nil
}Go 代码：有序数组转平衡 BST
这个题是在反过来利用“有序性”。
func SortedArrayToBST(nums []int) *TreeNode {
var build func(left, right int) *TreeNode
build = func(left, right int) *TreeNode {
if left > right {
return nil
}
mid := left + (right-left)/2
root := &TreeNode{Val: nums[mid]}
root.Left = build(left, mid-1)
root.Right = build(mid+1, right)
return root
}
return build(0, len(nums)-1)
}BST 最容易出错的地方
这几件事必须分清
- BST 的有序性是“整棵左子树 / 整棵右子树”的约束，不只是左右孩子比较。
- 删除两个孩子的节点时，常用后继节点替换，不要替换完忘了继续删后继。
- BST 平均复杂度是
O(log n)，最坏可以退化成链表变成O(n)。- 很多 BST 题的突破口不是树形 DP，而是中序遍历的有序序列。
平衡为什么重要
普通 BST 如果按升序插入：
1 -> 2 -> 3 -> 4 -> 5整棵树会退化成链表。
所以工程里更常见的是：
- 平衡二叉树
- 红黑树
- B 树 / B+ 树
也就是说，BST 更像“思想原型”，平衡树才是它的工程化版本。
复杂度
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
经典题目
- 二叉搜索树中的搜索 - LeetCode 700
- 二叉搜索树中的插入操作 - LeetCode 701
- 删除二叉搜索树中的节点 - LeetCode 450
- 验证二叉搜索树 - LeetCode 98
- 二叉搜索树中第 K 小的元素 - LeetCode 230
- 二叉搜索树的最近公共祖先 - LeetCode 235
- 将有序数组转换为二叉搜索树 - LeetCode 108