首先，BST 的特性大家应该都很熟悉了：
- 对于 BST 的每一个节点
node，左子树节点的值都比node的值要小，右子树节点的值都比node的值大。 - 对于 BST 的每一个节点
node，它的左侧子树和右侧子树都是 BST。
二叉搜索树并不算复杂，但我觉得它构建起了数据结构领域的半壁江山，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。
中序遍历有序性
从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。
也就是说，如果输入一棵 BST，以下代码可以将 BST 中每个节点的值升序打印出来：
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码位置
print(root.val);
traverse(root.right);
}那么根据这个性质，我们来做两道算法题。
寻找第 K 小的元素
首先是力扣第 230 题「二叉搜索树中第K小的元素」，看下题目：
这个需求很常见吧，一个直接的思路就是升序排序，然后找第k个元素呗。BST 的中序遍历其实就是升序排序的结果，找第k个元素肯定不是什么难事。
按照这个思路，可以直接写出代码：
int kthSmallest(TreeNode root, int k) {
// 利用 BST 的中序遍历特性
traverse(root, k);
return res;
}
// 记录结果
int res = 0;
// 记录当前元素的排名
int rank = 0;
void traverse(TreeNode root, int k) {
if (root == null) {
return;
}
traverse(root.left, k);
/* 中序遍历代码位置 */
rank++;
if (k == rank) {
// 找到第 k 小的元素
res = root.val;
return;
}
/*****************/
traverse(root.right, k);
}这道题就做完了，不过呢，还是要多说几句，因为这个解法并不是最高效的解法，而是仅仅适用于这道题。
我们旧文 高效计算数据流的中位数 中就提过今天的这个问题：
如果让你实现一个在二叉搜索树中通过排名计算对应元素的方法
select(int k)，你会怎么设计？
如果按照我们刚才说的方法，利用「BST 中序遍历就是升序排序结果」这个性质，每次寻找第k小的元素都要中序遍历一次，最坏的时间复杂度是O(N)，N是 BST 的节点个数。
要知道 BST 性质是非常牛逼的，像红黑树这种改良的自平衡 BST，增删查改都是O(logN)的复杂度，让你算一个第k小元素，时间复杂度竟然要O(N)，有点低效了。
所以说，计算第k小元素，最好的算法肯定也是对数级别的复杂度，不过这个依赖于 BST 节点记录的信息有多少。
我们想一下 BST 的操作为什么这么高效？就拿搜索某一个元素来说，BST 能够在对数时间找到该元素的根本原因还是在 BST 的定义里，左子树小右子树大嘛，所以每个节点都可以通过对比自身的值判断去左子树还是右子树搜索目标值，从而避免了全树遍历，达到对数级复杂度。
那么回到这个问题，想找到第k小的元素，或者说找到排名为k的元素，如果想达到对数级复杂度，关键也在于每个节点得知道他自己排第几。
比如说你让我查找排名为k的元素，当前节点知道自己排名第m，那么我可以比较m和k的大小：
1、如果m == k，显然就是找到了第k个元素，返回当前节点就行了。
2、如果k < m，那说明排名第k的元素在左子树，所以可以去左子树搜索第k个元素。
3、如果k > m，那说明排名第k的元素在右子树，所以可以去右子树搜索第k - m - 1个元素。
这样就可以将时间复杂度降到O(logN)了。
那么，如何让每一个节点知道自己的排名呢？
这就是我们之前说的，需要在二叉树节点中维护额外信息。每个节点需要记录，以自己为根的这棵二叉树有多少个节点。
也就是说，我们TreeNode中的字段应该如下：
class TreeNode {
int val;
// 以该节点为根的树的节点总数
int size;
TreeNode left;
TreeNode right;
}有了size字段，外加 BST 节点左小右大的性质，对于每个节点node就可以通过node.left推导出node的排名，从而做到我们刚才说到的对数级算法。
当然，size字段需要在增删元素的时候需要被正确维护，力扣提供的TreeNode是没有size这个字段的，所以我们这道题就只能利用 BST 中序遍历的特性实现了，但是我们上面说到的优化思路是 BST 的常见操作，还是有必要理解的。
BST 转化累加树
力扣第 538 题和 1038 题都是这道题，完全一样，你可以把它们一块做掉。看下题目：
题目应该不难理解，比如图中的节点 5，转化成累加树的话，比 5 大的节点有 6，7，8，加上 5 本身，所以累加树上这个节点的值应该是 5+6+7+8=26。
我们需要把 BST 转化成累加树，函数签名如下：
TreeNode convertBST(TreeNode root)按照二叉树的通用思路，需要思考每个节点应该做什么，但是这道题上很难想到什么思路。
BST 的每个节点左小右大，这似乎是一个有用的信息，既然累加和是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和，不就行了吗？
这是不行的。对于一个节点来说，确实右子树都是比它大的元素，但问题是它的父节点也可能是比它大的元素呀？这个没法确定的，我们又没有触达父节点的指针，所以二叉树的通用思路在这里用不了。
其实，正确的解法很简单，还是利用 BST 的中序遍历特性。
刚才我们说了 BST 的中序遍历代码可以升序打印节点的值：
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码位置
print(root.val);
traverse(root.right);
}那如果我想降序打印节点的值怎么办？
很简单，只要把递归顺序改一下就行了：
void traverse(TreeNode root) {
if (root == null) return;
// 先递归遍历右子树
traverse(root.right);
// 中序遍历代码位置
print(root.val);
// 后递归遍历左子树
traverse(root.left);
}这段代码可以从大到小降序打印 BST 节点的值，如果维护一个外部累加变量sum，然后把sum赋值给 BST 中的每一个节点，不就将 BST 转化成累加树了吗？
看下代码就明白了：
TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
// 记录累加和
int sum = 0;
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}这道题就解决了，核心还是 BST 的中序遍历特性，只不过我们修改了递归顺序，降序遍历 BST 的元素值，从而契合题目累加树的要求。
简单总结下吧，BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求，也就这么些事儿吧。
BST 的基础操作
接着来实现 BST 的基础操作：判断 BST 的合法性、增、删、查。其中「删」和「判断合法性」略微复杂。
判断 BST 的合法性
这里是有坑的哦，我们按照刚才的思路，每个节点自己要做的事不就是比较自己和左右孩子吗？看起来应该这样写代码：
boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (root.left != null && root.val <= root.left.val)
return false;
if (root.right != null && root.val >= root.right.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}但是这个算法出现了错误，BST 的每个节点应该要小于右边子树的所有节点，下面这个二叉树显然不是 BST，因为节点 10 的右子树中有一个节点 6，但是我们的算法会把它判定为合法 BST：
出现问题的原因在于，对于每一个节点root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root的整个左子树都要小于root.val，整个右子树都要大于root.val。
问题是，对于某一个节点root，他只能管得了自己的左右子节点，怎么把root的约束传递给左右子树呢？
请看正确的代码：
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。
在 BST 中搜索一个数
如果是在二叉树中寻找元素，可以这样写代码：
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target) return true;
// 当前节点没找到就递归地去左右子树寻找
return isInBST(root.left, target)
|| isInBST(root.right, target);
}这样写完全正确，但这段代码相当于穷举了所有节点，适用于所有普通二叉树。那么应该如何充分利用信息，把 BST 这个「左小右大」的特性用上？
很简单，其实不需要递归地搜索两边，类似二分查找思想，根据target和root.val的大小比较，就能排除一边。我们把上面的思路稍稍改动：
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val < target)
return isInBST(root.right, target);
if (root.val > target)
return isInBST(root.left, target);
// root 该做的事做完了，顺带把框架也完成了，妙
}于是，我们对原始框架进行改造，抽象出一套针对 BST 的遍历框架：
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}这个代码框架其实和二叉树的遍历框架差不多，无非就是利用了 BST 左小右大的特性而已。
在 BST 中插入一个数
对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」。具体到这个问题，插入一个数，就是先找到插入位置，然后进行插入操作。
上一个问题，我们总结了 BST 中的遍历框架，就是「找」的问题。直接套框架，加上「改」的操作即可。一旦涉及「改」，函数就要返回TreeNode类型，并且对递归调用的返回值进行接收。
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}在 BST 中删除一个数
这个问题稍微复杂，跟插入操作类似，先「找」再「改」，先把框架写出来再说：
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// 找到啦，进行删除
} else if (root.val > key) {
// 去左子树找
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// 去右子树找
root.right = deleteNode(root.right, key);
}
return root;
}找到目标节点了，比方说是节点A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。
情况 1：A恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
if (root.left == null && root.right == null)
return null;情况 2：A只有一个非空子节点，那么它要让这个孩子接替自己的位置。
// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;情况 3：A有两个子节点，麻烦了，为了不破坏 BST 的性质，A必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
if (root.left != null && root.right != null) {
// 找到右子树的最小节点
TreeNode minNode = getMin(root.right);
// 把 root 改成 minNode
root.val = minNode.val;
// 转而去删除 minNode
root.right = deleteNode(root.right, minNode.val);
}三种情况分析完毕，填入框架，简化一下代码：
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
TreeNode getMin(TreeNode node) {
// BST 最左边的就是最小的
while (node.left != null) node = node.left;
return node;
}删除操作就完成了。注意一下，这个删除操作并不完美，因为我们一般不会通过root.val = minNode.val修改节点内部的值来交换节点，而是通过一系列略微复杂的链表操作交换root和minNode两个节点。
因为具体应用中，val域可能会是一个复杂的数据结构，修改起来非常麻烦；而链表操作无非改一改指针，而不会去碰内部数据。
不过这里我们暂时忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维方式。
计算所有合法 BST
最后循序渐进地讲两道题，如何计算所有合法 BST。
第一道题是力扣第 96 题「不同的二叉搜索树」，给你输入一个正整数n，请你计算，存储{1,2,3...,n}这些值共有有多少种不同的 BST 结构。
函数签名如下：
int numTrees(int n);比如说输入n = 3，算法返回 5，因为共有如下 5 种不同的 BST 结构存储{1,2,3}：
这就是一个正宗的穷举问题，那么什么方式能够正确地穷举合法 BST 的数量呢？
我们前文说过，不要小看「穷举」，这是一件看起来简单但是比较有技术含量的事情，问题的关键就是不能数漏，也不能数多，你咋整？
之前 手把手刷二叉树第一期 说过，二叉树算法的关键就在于明确根节点需要做什么，其实 BST 作为一种特殊的二叉树，核心思路也是一样的。
举个例子，比如给算法输入n = 5，也就是说用{1,2,3,4,5}这些数字去构造 BST。
首先，这棵 BST 的根节点总共有几种情况？
显然有 5 种情况对吧，因为每个数字都可以作为根节点。
比如说我们固定3作为根节点，这个前提下能有几种不同的 BST 呢？
根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。
所以如果固定3作为根节点，左子树节点就是{1,2}的组合，右子树就是{4,5}的组合。
左子树的组合数和右子树的组合数乘积就是3作为根节点时的 BST 个数。
我们这是说了3为根节点这一种特殊情况，其实其他的节点也是一样的。
那你可能会问，我们可以一眼看出{1,2}和{4,5}有几种组合，但是怎么让算法进行计算呢？
其实很简单，只需要递归就行了，我们可以写这样一个函数：
// 定义：闭区间 [lo, hi] 的数字能组成 count(lo, hi) 种 BST
int count(int lo, int hi);根据这个函数的定义，结合刚才的分析，可以写出代码：
/* 主函数 */
int numTrees(int n) {
// 计算闭区间 [1, n] 组成的 BST 个数
return count(1, n);
}
/* 计算闭区间 [lo, hi] 组成的 BST 个数 */
int count(int lo, int hi) {
// base case
if (lo > hi) return 1;
int res = 0;
for (int i = lo; i <= hi; i++) {
// i 的值作为根节点 root
int left = count(lo, i - 1);
int right = count(i + 1, hi);
// 左右子树的组合数乘积是 BST 的总数
res += left * right;
}
return res;
}注意 base case，显然当lo > hi闭区间[lo, hi]肯定是个空区间，也就对应着空节点 null，虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0。
这样，题目的要求已经实现了，但是时间复杂度非常高，肯定存在重叠子问题。
前文动态规划相关的问题多次讲过消除重叠子问题的方法，无非就是加一个备忘录：
// 备忘录
int[][] memo;
int numTrees(int n) {
// 备忘录的值初始化为 0
memo = new int[n + 1][n + 1];
return count(1, n);
}
int count(int lo, int hi) {
if (lo > hi) return 1;
// 查备忘录
if (memo[lo][hi] != 0) {
return memo[lo][hi];
}
int res = 0;
for (int mid = lo; mid <= hi; mid++) {
int left = count(lo, mid - 1);
int right = count(mid + 1, hi);
res += left * right;
}
// 将结果存入备忘录
memo[lo][hi] = res;
return res;
}这样，这道题就完全解决了。
那么，如果给一个进阶题目，不止让你计算有几个不同的 BST，而是要你构建出所有合法的 BST，如何实现这个算法呢？
这道题就是力扣第 95 题「不同的二叉搜索树 II」，让你构建所有 BST，函数签名如下：
List<TreeNode> generateTrees(int n);比如说输入n = 3，算法返回一个列表，列表中存储着如下五棵 BST 的根节点：
明白了上道题构造合法 BST 的方法，这道题的思路也是一样的：
1、穷举root节点的所有可能。
2、递归构造出左右子树的所有合法 BST。
3、给root节点穷举所有左右子树的组合。
我们可以直接看代码：
/* 主函数 */
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<>();
// 构造闭区间 [1, n] 组成的 BST
return build(1, n);
}
/* 构造闭区间 [lo, hi] 组成的 BST */
List<TreeNode> build(int lo, int hi) {
List<TreeNode> res = new LinkedList<>();
// base case
if (lo > hi) {
res.add(null);
return res;
}
// 1、穷举 root 节点的所有可能。
for (int i = lo; i <= hi; i++) {
// 2、递归构造出左右子树的所有合法 BST。
List<TreeNode> leftTree = build(lo, i - 1);
List<TreeNode> rightTree = build(i + 1, hi);
// 3、给 root 节点穷举所有左右子树的组合。
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {
// i 作为根节点 root 的值
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}这样，两道题都解决了。
二叉搜索树查找lower_bound
题目描述
Leecode周赛6242. Closest Nodes Queries in a Binary Search Tree
You are given the root of a binary search tree and an array queries of size n consisting of positive integers.
Find a 2D array answer of size n where answer[i] = [mini, maxi]:
miniis the largest value in the tree that is smaller than or equal toqueries[i]. If a such value does not exist, add-1instead.maxiis the smallest value in the tree that is greater than or equal toqueries[i]. If a such value does not exist, add-1instead.
Return the arrayanswer.
Example 1:
Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: We answer the queries in the following way:
- The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
- The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
- The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].解题方法1
首先，题目没说二叉搜索树是平衡的，最坏情况下二叉搜索树是一条链。
因此需要通过一次 94. 二叉树的中序遍历 得到有一个有序数组，再在数组上做二分查找。
在有序数组中求大于等于和小于等于，和 34. 在排序数组中查找元素的第一个和最后一个位置 是一样的。这里使用lower_bound即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
void serialize(TreeNode* root, vector<int>& sorted){
if(!root) return;
serialize(root->left,sorted);
sorted.emplace_back(root->val);
serialize(root->right,sorted);
}
public:
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
// sort
vector<int> sorted;
serialize(root,sorted);
vector<vector<int>> res;
for(auto& num:queries){
vector<int>::iterator maxi = lower_bound(sorted.begin(),sorted.end(),num);
int index = maxi - sorted.begin();
if(maxi==sorted.end()){
res.push_back(vector<int>{sorted[sorted.size()-1],-1});
}else if(*maxi==num){
res.push_back(vector<int>{num,num});
}else if(index==0){
res.push_back(vector<int>{-1,sorted[index]});
}else{
res.push_back(vector<int>{sorted[index - 1],sorted[index]});
}
}
return res;
}
};解题方法2
我们考虑二分搜索树搜索目标值的几个性质：
- 如果当前值等于目标值，最接近的值显然是当前值
- 如果当前值小于目标值，则比目标值小的元素中最大的值(
mini)至少不比当前值小；我们应该往右节点方向搜索，往大的方向搜索 - 如果当前值大于目标值，则比目标值大的元素中最小的值(
maxi)至少不比当前值大；我们应该往左节点方向搜索，往小的方向搜索
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> find(TreeNode* root, int target) {
int smaller=root->val;
int larger=root->val;
vector<int> ans(2, 0);
while (root) {
if (root->val == target) {
ans[0] = target;
ans[1] = target;
return ans;
}
if (root->val > target) {
larger = root->val;
root = root->left;
} else {
smaller = root->val;
root = root->right;
}
}
ans[0] = smaller <= target ? smaller : -1;
ans[1] = larger >= target ? larger : -1;
return ans;
}
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
int n = queries.size();
vector<vector<int>> ans(n, vector<int>(2, -1));
for (int i = 0; i < n; i++) {
int q = queries[i];
ans[i] = find(root, q);
}
return ans;
}
};复杂度
- 时间复杂度: \(O(q*n)\)，如果树平衡则为 \(O(q*log(n))\)
- 空间复杂度: \(O(q)\)
最后总结
通过这篇文章，我们总结出了如下几个技巧：
1、如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
2、在二叉树递归框架之上，扩展出一套 BST 代码框架：
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}3、根据代码框架掌握了 BST 的增删查改操作。