东哥带你刷二叉搜索树（特性篇）
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
———–
本文有视频版： 动手实现 TreeMap。
前文手把手带你刷二叉树已经写了 第一期， 第二期 和 第三期，今天写一篇二叉搜索树（Binary Search Tree，后文简写 BST）相关的文章，手把手带你刷 BST。
首先，BST 的特性大家应该都很熟悉了：
1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
2、对于 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);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void traverse(TreeNode* root)
{
if (root == nullptr)
{
return;
}
traverse(root->left);
// 中序遍历代码位置
print(root->val);
traverse(root->right);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def traverse(root):
if not root:
return
traverse(root.left)
# 中序遍历代码位置
print(root.val)
traverse(root.right)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func traverse(root *TreeNode) {
if root == nil {
return
}
traverse(root.left)
// 中序遍历代码位置
fmt.Println(root.val)
traverse(root.right)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var traverse = function(root) {
if (root === null) return;
traverse(root.left);
// 中序遍历代码位置
console.log(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);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int kthSmallest(TreeNode* root, int k) {
// 利用 BST 的中序遍历特性
traverse(root, k);
return res;
}
// 记录结果
int res = 0;
// 记录当前元素的排名
int rank = 0;
void traverse(TreeNode* root, int k, int& res, int& rank) {
if (!root) {
return;
}
traverse(root->left, k, res, rank);
/* 中序遍历代码位置 */
rank++;
if (k == rank) {
// 找到第 k 小的元素
res = root->val;
return;
}
/*****************/
traverse(root->right, k, res, rank);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def kthSmallest(root: TreeNode, k: int) -> int:
# 利用 BST 的中序遍历特性
traverse(root, k)
return res
# 记录结果
res = 0
# 记录当前元素的排名
rank = 0
def traverse(root: TreeNode, k: int) -> None:
global res
global rank
if not root:
return
traverse(root.left, k)
# 中序遍历代码位置
rank += 1
if k == rank:
# 找到第 k 小的元素
res = root.val
return
traverse(root.right, k)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func kthSmallest(root *TreeNode, k int) int {
// 利用 BST 的中序遍历特性
res := 0
rank := 0
traverse(root, k, &res, &rank)
return res
}
// 记录结果
// 注意：这里是指针类型，因为需要在函数内修改其值
// res 表示第 k 小的元素的值
func traverse(root *TreeNode, k int, res *int, rank *int) {
if root == nil {
return
}
traverse(root.Left, k, res, rank)
/* 中序遍历代码位置 */
*rank++
if k == *rank {
// 找到第 k 小的元素
*res = root.Val
return
}
/*****************/
traverse(root.Right, k, res, rank)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var kthSmallest = function(root, k) {
// 利用 BST 的中序遍历特性
traverse(root, k);
return res;
}
// 记录结果
var res = 0;
// 记录当前元素的排名
var rank = 0;
function traverse(root, 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)，你会怎么设计？
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;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class TreeNode {
public:
int val;
// 以该节点为根的树的节点总数
int size;
TreeNode* left;
TreeNode* right;
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class TreeNode:
def __init__(self):
self.val = None
# 以该节点为根的树的节点总数
self.size = None
self.left = None
self.right = None
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
type TreeNode struct {
Val int // 该节点的值
Size int // 以该节点为根的树的节点总数
Left *TreeNode // 左子节点
Right *TreeNode // 右子节点
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
function TreeNode() {
var val;
// 以该节点为根的树的节点总数
var size;
var left;
var 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)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* convertBST(TreeNode* root);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def convertBST(root: TreeNode) -> TreeNode:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func convertBST(root *TreeNode) *TreeNode {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var convertBST = function(root) {}
按照二叉树的通用思路，需要思考每个节点应该做什么，但是这道题上很难想到什么思路。
BST 的每个节点左小右大，这似乎是一个有用的信息，既然累加和是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和，不就行了吗？
这是不行的。对于一个节点来说，确实右子树都是比它大的元素，但问题是它的父节点也可能是比它大的元素呀？这个没法确定的，我们又没有触达父节点的指针，所以二叉树的通用思路在这里用不了。
其实，正确的解法很简单，还是利用 BST 的中序遍历特性。
刚才我们说了 BST 的中序遍历代码可以升序打印节点的值：
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码位置
print(root.val);
traverse(root.right);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void traverse(TreeNode* root)
{
if (root == nullptr)
{
return;
}
traverse(root->left);
// 中序遍历代码位置
print(root->val);
traverse(root->right);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def traverse(root):
if not root:
return
traverse(root.left)
# 中序遍历代码位置
print(root.val)
traverse(root.right)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func traverse(root *TreeNode) {
if root == nil {
return
}
traverse(root.left)
// 中序遍历代码位置
fmt.Println(root.val)
traverse(root.right)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var traverse = function(root) {
if (root === null) return;
traverse(root.left);
// 中序遍历代码位置
console.log(root.val);
traverse(root.right);
};
那如果我想降序打印节点的值怎么办？
很简单，只要把递归顺序改一下就行了：
void traverse(TreeNode root) {
if (root == null) return;
// 先递归遍历右子树
traverse(root.right);
// 中序遍历代码位置
print(root.val);
// 后递归遍历左子树
traverse(root.left);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void traverse(TreeNode* root) {
if (root == nullptr) return;
// 先递归遍历右子树
traverse(root->right);
// 中序遍历代码位置
print(root->val);
// 后递归遍历左子树
traverse(root->left);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def traverse(root):
if root is None:
return
traverse(root.right)
# 中序遍历代码位置
print(root.val)
traverse(root.left)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func traverse(root *TreeNode) {
if root == nil {
return
}
// 先递归遍历右子树
traverse(root.Right)
// 中序遍历代码位置
fmt.Println(root.Val)
// 后递归遍历左子树
traverse(root.Left)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var traverse = function(root) {
if (root == null) return;
// 先递归遍历右子树
traverse(root.right);
// 中序遍历代码位置
console.log(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);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* convertBST(TreeNode* root) {
traverse(root);
return root;
}
//记录累加和
int sum = 0;
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
traverse(root->right);
//维护累加和
sum += root->val;
//将BST转化成累加树
root->val = sum;
traverse(root->left);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def convertBST(root: TreeNode) -> TreeNode:
# 记录累加和
sum = [0]
def traverse(root):
if not root:
return
traverse(root.right)
# 维护累加和
sum[0] += root.val
# 将 BST 转化成累加树
root.val = sum[0]
traverse(root.left)
traverse(root)
return root
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func convertBST(root *TreeNode) *TreeNode {
traverse(root)
return root
}
// 记录累加和
var sum int
func traverse(root *TreeNode) {
if root == nil {
return
}
traverse(root.Right)
// 维护累加和
sum += root.Val
// 将 BST 转化成累加树
root.Val = sum
traverse(root.Left)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function(root) {
traverse(root);
return root;
};
// 记录累加和
let sum = 0;
function traverse(root) {
if (root == null) {
return;
}
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}
🎃 代码可视化动画 🎃
这道题就解决了，核心还是 BST 的中序遍历特性，只不过我们修改了递归顺序，降序遍历 BST 的元素值，从而契合题目累加树的要求。
简单总结下吧，BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求，也就这么些事儿吧。
当然，BST 还可以玩出更多花样，提供更丰富的 API，更多内容参见我的数据结构课程中的 动手实现 TreeMap 章节。
本文就到这里，更多经典的二叉树习题以及递归思维的训练，请参见 手把手带你刷通二叉树。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释