labuladong 手把手刷二叉搜索树(第一期)
NOTE:
LeetCode 230. 二叉搜索树中第K小的元素 中等
LeetCode 538. 把二叉搜索树转换为累加树 中等
寻找第 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);
}
这道题就做完了,不过呢,还是要多说几句,因为**这个解法并不是最高效的解法,而是仅仅适用于这道题。**
更加高效的解法
NOTE:
一、典型的以空间换时间,skip list中,也有类似的优化方式,参见 "wikipedia Skip list # Indexable skiplist" 章节
我们旧文 高效计算数据流的中位数 中就提过今天的这个问题:
如果让你实现一个在二叉搜索树中通过排名计算对应元素的方法
select(int k)
,你会怎么设计?
如果按照我们刚才说的方法,利用「BST 中序遍历就是升序排序结果」这个性质,每次寻找第k
小的元素都要中序遍历一次,最坏的时间复杂度是O(N)
,N
是 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 左小右大的特性提升算法效率,要么利用中序遍历的特性满足题目的要求,也就这么些事儿吧。