一、BST 的核心性质：有序是灵魂
二叉搜索树，说白了就是一棵「有序」的二叉树。我刚开始学的时候，总觉得它跟普通二叉树没啥区别，直到在项目中栽了跟头才明白——BST 的一切操作，都建立在「有序」这两个字上。
1.1 定义与性质
BST 的定义其实很简单，就三条：
- 左子树所有节点的值 < 根节点的值
- 右子树所有节点的值 > 根节点的值
- 左右子树也分别是 BST
嗯，这里要注意：是「所有」节点，不是「直接子节点」。我曾经在代码审查时看到有人只比较了当前节点和左右孩子，结果整棵树根本不是 BST 却没发现。
1.2 为什么中序遍历是递增的？
你想想看，中序遍历的顺序是「左-根-右」。左子树所有值都比根小，右子树所有值都比根大，那遍历出来自然就是从小到大。反过来，如果一棵二叉树的中序遍历不是递增的，那它肯定不是 BST。
我个人习惯用这个性质来快速判断 BST 的合法性，比递归判断左右子树范围要直观得多。
二、BST 的查找：二分思想的树形体现
BST 的查找其实就是二分查找的树形版本。每次比较都能排除一半的子树，时间复杂度 O(log n)。
// 递归版查找
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) return root;
if (val < root->val) return searchBST(root->left, val);
else return searchBST(root->right, val);
}
// 迭代版查找（我更喜欢这个，省栈空间）
TreeNode* searchBST(TreeNode* root, int val) {
while (root && root->val != val) {
if (val < root->val) root = root->left;
else root = root->right;
}
return root;
}三、BST 的插入：找到位置就挂上去
插入操作的核心思想是：先查找，找不到就插入。说白了就是沿着 BST 的路径往下走，直到找到一个空位置。
TreeNode* insertBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val) {
root->left = insertBST(root->left, val);
} else if (val > root->val) {
root->right = insertBST(root->right, val);
}
// 如果相等，根据需求处理，通常不插入重复值
return root;
}这里有个细节：插入的节点一定是叶子节点。为什么？因为 BST 的查找路径是唯一的，你找到的空位置就是叶子节点的孩子位置。
四、BST 的删除：三种情况，三种处理
删除是 BST 操作中最麻烦的。我刚开始学的时候，总觉得逻辑绕来绕去，后来总结成三种情况就好理解了：
| 情况 | 描述 | 处理方法 |
|---|---|---|
| 情况一 | 叶子节点（无孩子） | 直接删除，父节点对应指针置空 |
| 情况二 | 只有一个孩子 | 用孩子替换当前节点 |
| 情况三 | 有两个孩子 | 找右子树的最小节点（或左子树的最大节点）替换当前节点，然后删除那个节点 |
TreeNode* deleteBST(TreeNode* root, int val) {
if (!root) return nullptr;
if (val < root->val) {
root->left = deleteBST(root->left, val);
} else if (val > root->val) {
root->right = deleteBST(root->right, val);
} else {
// 找到要删除的节点
if (!root->left) {
// 情况一（无孩子）和情况二（只有右孩子）合并处理
TreeNode* temp = root->right;
delete root;
return temp;
} else if (!root->right) {
// 情况二（只有左孩子）
TreeNode* temp = root->left;
delete root;
return temp;
}
// 情况三：有两个孩子
// 找右子树的最小节点
TreeNode* minNode = findMin(root->right);
root->val = minNode->val;
root->right = deleteBST(root->right, minNode->val);
}
return root;
}
TreeNode* findMin(TreeNode* root) {
while (root->left) root = root->left;
return root;
}五、经典例题：验证二叉搜索树
这道题是面试高频题，也是检验你是否真正理解 BST 性质的试金石。
5.1 题目描述
给定一个二叉树，判断它是否是有效的二叉搜索树。
5.2 解法一：中序遍历法
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* pre = nullptr;
while (root || !st.empty()) {
while (root) {
st.push(root);
root = root->left;
}
root = st.top(); st.pop();
// 检查当前节点是否大于前一个节点
if (pre && root->val <= pre->val) return false;
pre = root;
root = root->right;
}
return true;
}这个解法的时间复杂度 O(n)，空间复杂度 O(n)。我个人比较推荐这个写法，因为思路清晰，不容易出错。
5.3 解法二：递归范围法
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
bool validate(TreeNode* root, long minVal, long maxVal) {
if (!root) return true;
if (root->val <= minVal || root->val >= maxVal) return false;
return validate(root->left, minVal, root->val)
&& validate(root->right, root->val, maxVal);
}这里用 LONG_MIN 和 LONG_MAX 是因为测试用例中可能出现 INT_MIN 和 INT_MAX 的值。嗯，这个坑我踩过，当时 debug 了半天才发现是边界问题。
六、经典例题：最近公共祖先（LCA）
BST 的 LCA 问题比普通二叉树的 LCA 简单得多，因为我们可以利用 BST 的有序性质。
6.1 题目描述
给定一个 BST 和两个节点 p、q，找到它们的最近公共祖先。
6.2 核心思路
从根节点开始遍历：
- 如果 p 和 q 都在左子树，往左走
- 如果 p 和 q 都在右子树，往右走
- 否则，当前节点就是 LCA（一个在左一个在右，或者当前节点就是 p 或 q）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
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 nullptr;
}这个解法的时间复杂度 O(h)，其中 h 是树的高度。空间复杂度 O(1)，因为用的是迭代。
七、知识体系总览
下面这张图总结了 BST 的核心知识点和它们之间的关系：
八、总结与避坑
BST 这块内容，说难不难，说简单也不简单。我总结几个容易踩的坑：
- 验证 BST 时只比较左右孩子——这是最常见的错误。记住要比较「所有」左子树节点和「所有」右子树节点。
- 删除操作忘记处理内存——C++ 中要 delete 节点，Java/Python 虽然不用手动释放，但逻辑上要清楚。
- 递归深度过大——BST 可能退化成链表，递归写法要小心栈溢出。
- 边界值处理——验证 BST 时，如果节点值恰好是 INT_MIN 或 INT_MAX，用 int 做边界会出问题。