二叉搜索树（Binary Search Tree）简称 BST，是二叉树的一种特殊形式。它有很多别名，比如排序二叉树、二叉查找树等等。
虽然二叉搜索树多年来一直作为算法面试的“必要考点”存在，但在实际面试中，它的考察频率并不能和常规二叉树相提并论，算不上“大热”的考点，同时考察内容也是相对比较稳定的。对于二叉搜索树，我们只要能够把握好它的限制条件和特性，就足以应对大部分的考题。
# 什么是二叉搜索树
30 秒速记
BST= 左子树全部 ≤ 根 ≤ 右子树全部，而且每棵子树都这样，递归定义，空树也算- 约束管的是「整棵子树」，不是只看直接孩子：根
10的左子树里藏个12就不合法 - 等价特征：中序遍历有序（无重复时严格递增）
- 操作都是
O(h)：平衡时O(log n)，有序插入退化成链就是O(n) - 重复值放哪边是约定问题，插入、查找、验证要用同一套规则
二叉搜索树说白了就是把「二分查找」做成了一棵树：左边都比根小，右边都比根大，而且每一棵子树都守这个规矩。 所以从根往下找，每比一次就能扔掉一半。很多人写验证只比父子，这是错的，比如根是 10，左孩子 5，5 的右孩子是 12，局部看 5 < 12 没毛病，但 12 跑到了 10 的左边，整棵树就不成立了。另外它的快是有条件的，树高才是复杂度，顺序插入 1,2,3,4,5 会长成一条链，查找就退回 O(n)。
树的定义总是以递归的形式出现，二叉搜索树也不例外，它的递归定义如下：
- 是一棵空树
- 是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域
满足以上两个条件之一的二叉树，就是二叉搜索树。
从这个定义我们可以看出，二叉搜索树强调的是数据域的有序性。也就是说，二叉搜索树上的每一棵子树，都应该满足
左孩子 <= 根结点 <= 右孩子这样的大小关系。下图我给出了几个二叉搜索树的示例
以第三棵树为例，根结点的数据域为6，它的左子树的所有结点都小于等于6、右子树的所有结点都大于等于6。同时在任意子树的内部，也满足这个条件——比如左子树中，根结点值为3，根结点对应左子树的所有结点都小于等于3、右子树的所有结点都大于等于3。
面试官追问
追问 1根 10、左孩子 5、5 的右孩子 12，这是 BST 吗？
不是。12 在 10 的左子树里，必须小于 10。只比较父子 5 < 12 会误判，验证时要把祖先给的上下界一路带下去。
追问 2中序遍历结果是有序的，能反推它就是 BST 吗？
无重复值时可以，中序严格递增和 BST 是等价的，LeetCode 98 用中序 + 记录上一个值也能过。有重复值时要看约定，比如规定相等只能放右边，那光看非递减序列就判断不出来。
追问 3BST 查找号称 O(log n)，为什么有人实测和遍历数组差不多？
大概率是数据按顺序插入的，树退化成了单链，高度等于 n。O(log n) 只在树平衡时成立，要稳定就上 AVL、红黑树这类自平衡结构。
追问 4数据加载后不再改，只按值查，用 BST 还是有序数组？
我选有序数组 + 二分。一样是 O(log n)，数组内存连续、缓存友好，还能按下标取第 k 个。BST 的优势在于频繁插删不用整体搬元素。
追问 5允许重复键的话怎么设计比较省心？
最省事的是一个结点存一个 count，重复插入只加计数，树里永远没有相等的结点，查找和删除都不用纠结往哪边走。
# 二叉搜索树：编码基本功
30 秒速记
- 三件套：查找、插入、删除，都是「从根开始比大小，只走一边」
- 插入 = 查找走到空位，把新结点挂上去
- 递归修改型函数要返回子树新根，调用方写
root.left = insert(root.left, n)接回去 - 删除分三种：叶子直接删 / 一个孩子顶上来 / 两个孩子找前驱或后继替换
- 复杂度都是
O(h)，别脱口而出O(log n)
BST 的三个基本操作其实是同一个套路：从根出发比大小，小了往左、大了往右，只走一条路。 查找走到空就是没找到；插入就是把新结点放在查找失败的那个空位上；删除麻烦一点，要分叶子、单孩子、双孩子三种。写代码最容易翻车的是递归改结构时不接返回值，比如只写了 insert(root.left, n) 而不是 root.left = insert(root.left, n)，新结点就挂不上去。复杂度我会说 O(h)，再补一句平衡时才是 O(log n)。
关于二叉搜索树，大家需要掌握以下高频操作：
- 查找数据域为某一特定值的结点
- 插入新结点
- 删除指定结点
面试官追问
追问 1递归插入写成 insert(root.left, n)，没报错但树没变，为什么？
函数里给空位 root = new TreeNode(n) 只是改了局部变量，父结点的 left 还是 null。要写成 root.left = insert(root.left, n)，让返回的子树根接回去。
追问 2查找能不能不用递归？
能，而且更推荐：while (node && node.val !== n) node = n < node.val ? node.left : node.right。退化成链时递归深度等于 n，几万个结点就可能爆栈。
追问 3这三个操作哪个最容易写错？
删除。双孩子那种情况替换完值以后，还得去子树里把原来那个前驱或后继删掉，很多人只复制了值，树里就多出一个重复结点。
追问 4调用方删除根结点后，外面拿到的还是旧树，问题在哪？
根结点没有父结点帮你回接，删完新根可能变了，调用方必须写 root = deleteNode(root, key)。只调函数不接返回值，里面改得再对外面也看不到。
# 查找数据域为某一特定值的结点
30 秒速记
- 相等返回；目标小走左，目标大走右；走到
null= 不存在 - 每层只看一个结点，复杂度
O(h) - 迭代写法更稳，链状深树不会爆栈
- 找到要
return结点，别只console.log，调用方拿不到结果
查找就是拿目标值和当前结点比：相等就找到了，小就去左边，大就去右边，走到空结点说明树里没有。 它快的原因是每一步都排除掉另一整棵子树，所以耗时取决于树有多高，不是有多少结点。实际写我更喜欢迭代：
function search(root, n) {
let node = root
while (node && node.val !== n) {
node = n < node.val ? node.left : node.right
}
return node // 找不到时是 null
}
上面那段示例只打印不返回，面试写的时候记得改成返回结点。
假设这个目标结点的数据域值为 n，我们借助二叉搜索树数据域的有序性，可以有以下查找思路：
- 递归遍历二叉树，若当前遍历到的结点为空，就意味着没找到目标结点，直接返回。
- 若当前遍历到的结点对应的数据域值刚好等于n，则查找成功，返回。
- 若当前遍历到的结点对应的数据域值大于目标值n，则应该在左子树里进一步查找，设置下一步的遍历范围为 root.left 后，继续递归。
- 若当前遍历到的结点对应的数据域值小于目标值n，则应该在右子树里进一步查找，设置下一步的遍历范围为 root.right 后，继续递归。
编码实现
function search(root, n) {
// 若 root 为空，查找失败，直接返回
if(!root) {
return
}
// 找到目标结点，输出结点对象
if(root.val === n) {
console.log('目标结点是：', root)
} else if(root.val > n) {
// 当前结点数据域大于n，向左查找
search(root.left, n)
} else {
// 当前结点数据域小于n，向右查找
search(root.right, n)
}
}
面试官追问
追问 1search 递归时递归调用前没写 return，有什么问题？
找到了也只是在最深那层打印，外层拿到的永远是 undefined。要写 return search(root.left, n)，结果才能一层层带回来。
追问 2一棵 10 万个结点的 BST，查找最坏要比较几次？
看高度。平衡的话大约 17 次（log2(100000) ≈ 17），退化成链就是 10 万次。所以说复杂度一定带上 h。
追问 3怎么找树里最小值和最大值？
最小值一路往左走到底，最大值一路往右走到底，都是 O(h)。删除双孩子结点时找前驱、后继用的就是这两个函数。
追问 4要找「小于等于 x 的最大值」怎么改？
还是按大小走：当前值 ≤ x 就先记下来再往右找更大的，> x 就往左。走到空时最后记下的就是答案，这也是 floor 查询的标准写法。
# 插入新结点
30 秒速记
- 插入 = 查找失败的那个空位，新结点永远挂成叶子
- 递归返回子树根：空位处
return new TreeNode(n)，上层root.left/right = ...接回 - 先定重复值策略：忽略 / 计数 / 固定放右边
O(h)；按顺序插入1..n会退化成链
插入其实就是一次查找：按大小一路往下走，走到哪个空位，新结点就放在哪。 道理很简单，那个位置如果有值为 n 的结点，刚才那次查找就成功了，所以把 n
