二叉搜索树
- 二叉搜索树 BST
- BST 的基本操作
- 计算合法的 BST
图片来源于网络
1. 二叉搜索树 BST
二叉搜索树（Binary Search Tree），简写 BST，其特性如下：
- 对于 BST 的每一个节点
node，左子树节点的值都比node的值要小，右子树节点的值都比node的值大。 - 对于 BST 的每一个节点
node，它的左侧子树和右侧子树都是 BST。
基于 BST 的数据结构有 AVL 树，红黑树等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。
BST 还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。其遍历框架如下：
/**
* 遍历框架
*/
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码...
traverse(root.right);
}
1.1 寻找第 K 小的元素
/**
* 230 题「二叉搜索树中第K小的元素」
* <p>
* 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
* <p>
* 假设 k 总是有效的，1 <= k <= 二叉搜索树元素个数
* <p>
* 输入：root = [5,3,6,2,4,null,null,1]，k=3
* // 5
* // / \
* // 3 6
* // / \
* // 2 4
* // /
* // 1
* 输出：3
*/
private int kthSmallest(TreeNode root, int k) {
// 利用 BST 的中序遍历特性
traverse(root, k);
return res;
}
int res = 0; // 记录结果
int rank = 0; // 记录当前元素的排名
private 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);
}
值得注意的是，上面的解法是利用「BST 中序遍历就是升序排序结果」这个性质来的，并不是最高效的解法，这个解法仅仅适用于上面这道题。
1.2 BST 转化累加树
力扣 538 和 1038 题，如下：
把二叉搜索树转化为累加树
这道题还是利用 BST 的中序遍历特性，只不过需要修改递归顺序，降序遍历 BST 的元素值：
/**
* 538 题、1038 题：BST 转化累加树
* <p>
* 给出二叉搜索树的根节点，该树的节点值各不相同，将其转换为累加树（Greater Sum Tree），
* 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
* <p>
* BST 的中序遍历代码可以升序打印节点的值，所以想降序打印节点的值只要把递归顺序改一下：先递归右子树再递归左子树
*/
private TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
int sum = 0;// 记录累加和
private void traverse(TreeNode root) {
if (root == null) return;
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}
小结：BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求。
2. BST 的基本操作
2.1 判断 BST 的合法性
根据 BST 的定义，root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val：
/**
* 判断 BST 的合法性
*/
private boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/**
* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val
*/
private 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);
}
值得注意的是：上面通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点。
小结：如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
2.2 在 BST 中搜索一个数
若在二叉树中寻找元素，很容易写出如下代码：
/**
* 在二叉树中搜索一个数
* <p>
* 这段代码相当于穷举了所有节点，适用于所有普通二叉树
*/
private 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 这个「左小右大」的特性用上，可改为如下：
/**
* 在 BST 中搜索一个数
* <p>
* 用上 BST 这个「左小右大」的特性
*/
private 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);
}
小结：针对 BST 的遍历框架如下：
/**
* 针对 BST 的遍历框架
* <p>
* 利用了 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);
}
2.3 在 BST 中插入一个数
对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」，一旦涉及「改」，函数就要返回 TreeNode 类型，并且对递归调用的返回值进行接收：
/**
* 在 BST 中插入一个数
*/
private 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;
}
2.4 在 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;
}
在 BST 中删除一个节点 A 有 3 种情况：
-
A是末端节点，两个子节点都为空。 -
A只有一个非空子节点，那么它要让这个子节点接替自己的位置。 -
A有两个子节点，为了不破坏 BST 的性质，A必须找到左子树中最大的那个节点，或右子树中最小的那个节点来接替自己的位置。
/**
* 在 BST 中删除一个数
* <p>
* 注：这个删除操作并不完美，因为一般不会通过root.val = minNode.val修改节点内部的值来交换节点，
* 而是通过一系列略微复杂的链表操作交换root和minNode两个节点。
* <p>
* 具体应用中，val域可能会是一个复杂的数据结构，修改起来非常麻烦；而链表操作无非改一改指针，而不会去碰内部数据。
*/
private TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 找到了进行删除：
// 1. A 是末端节点，两个子节点都为空
if (root.left == null && root.right == null) return null;
// 2. A 只有一个非空子节点，那么它要让这个子节点接替自己的位置
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);
}
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
root.left = deleteNode(root.left, key);
}
return root;
}
TreeNode getMin(TreeNode node) {
// BST 最左边的就是最小的
while (node.left != null) node = node.left;
return node;
}
小结：根据代码框架进行 BST 的增删查改操作。
3. 计算合法的 BST
之前文章有说过二叉树算法的关键就在于明确根节点需要做什么，而 BST 作为一种特殊的二叉树，核心思路也是一样的。
3.1 不同的二叉搜索树 I
/**
* 不同的二叉搜索树
* <p>
* 输入一个正整数n，请你计算，存储{1,2,3...,n}这些值共有多少种不同的 BST 结构
* <p>
* 如：输入n = 3，算法返回 5，因为共有如下 5 种不同的 BST 结构存储{1,2,3}
* <p>
* // 1 3 3 2 1
* // \ / / / \ \
* // 3 2 1 1 3 2
* // / / \ \
* // 2 1 2 3
*/
private int numTrees(int n) {
// 计算闭区间 [1, n] 组成的 BST 个数
return count(1, n);
}
/**
* 定义：闭区间 [low, high] 的数字能组成 count(low, high) 种 BST
*/
private int count(int low, int high) {
// base case
if (low > high) return 1;
int res = 0;
for (int i = low; i <= high; i++) {
// i 的值作为根节点 root
int left = count(low, i - 1);
int right = count(i + 1, high);
// 左右子树的组合数乘积是 BST 的总数
res += left * right;
}
return res;
}
值得注意的是，上面算法时间复杂度非常高，存在重叠子问题，因此可以添加一个备忘录：
/**
* 通过添加一个备忘录来改进上面的算法
*/
int[][] memo; // 备忘录
int numTreesNew(int n) {
// 备忘录的值初始化为 0
memo = new int[n + 1][n + 1];
return countNew(1, n);
}
int countNew(int low, int high) {
if (low > high) return 1;
// 查备忘录
if (memo[low][high] != 0) {
return memo[low][high];
}
int res = 0;
for (int mid = low; mid <= high; mid++) {
int left = countNew(low, mid - 1);
int right = countNew(mid + 1, high);
res += left * right;
}
// 将结果存入备忘录
memo[low][high] = res;
return res;
}
3.2 不同的二叉搜索树 II
/**
* 不同的二叉搜索树 II
* 如：输入n = 3，算法返回一个列表，列表中存储着如下五棵 BST 的根节点：
* <p>
* // 1 3 3 2 1
* // \ / / / \ \
* // 3 2 1 1 3 2
* // / / \ \
* // 2 1 2 3
* <p>
* 1、穷举root节点的所有可能。
* <p>
* 2、递归构造出左右子树的所有合法 BST。
* <p>
* 3、给root节点穷举所有左右子树的组合。
*/
private List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<>();
// 构造闭区间 [1, n] 组成的 BST
return build(1, n);
}
/**
* 构造闭区间 [low, high] 组成的 BST
*/
private List<TreeNode> build(int low, int high) {
List<TreeNode> res = new LinkedList<>();
// base case
if (low > high) {
res.add(null);
return res;
}
// 1、穷举 root 节点的所有可能。
for (int i = low; i <= high; i++) {
// 2、递归构造出左右子树的所有合法 BST。
List<TreeNode> leftTree = build(low, i - 1);
List<TreeNode> rightTree = build(i + 1, high);
// 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;
}
参考链接：
