二叉搜索树第一期

01 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

直接的思路就是升序排序，然后寻找第 k 个元素即可。BST 的中序遍历就是升序排序的结果。

  1. // 记录结果
  2. int res = 0;
  3. // 记录当前元素的排名
  4. int rank = 0;
  5. void traverse(TreeNode* root, int k) {
  6.     if (root == nullptr)
  7.         return;
  8.     traverse(root->left, k);
  9.     // 中序遍历代码位置
  10.     rank++;
  11.     if (k == rank) {
  12.         res = root->val;
  13.         return;
  14.     }
  15.     traverse(root->right, k);
  16. }
  18. int kthSmallest(TreeNdoe* root, int k) {
  19.     traverse(root, k);
  20.     return res;
  21. }

但是这个解法不是最高效的。

按照我们刚才说的方法，利用「BST 中序遍历就是升序排序的结果」这个性质，每次寻找第 k 小的元素都要中序遍历一次，最坏的时间复杂度是 O(N)，N 是 BST 的节点个数。

如果想要达到对数级复杂度，关键在于每个节点知道他自己排第几。

02 把二叉搜索树转换为累加树

2.2.1 二叉搜索树第一期 - 图1

如图所示，比如图中的节点 5，转成累加树的话，比 5 大的节点有 6， 7， 8，加上 5 本身，所以累加树上的这个节点的值应该是 26。

一个简单的思路就是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和不就行了吗？

这是不行的。对于一个节点来说，右子树都是比它大的元素，但是它的父节点也可能是比它大的元素。其实，可以将 BST 降序打印即可。维护一个外部变量 sum，然后把 sum 赋值给 BST 中的每一个节点。

  1. int sum = 0;
  2. void traverse(TreeNode* root) {
  3.     if (root == nullptr)
  4.         return;
  5.     traverse(root->right);
  6.     // 维护累加树
  7.     sum += root->val;
  8.     // 将 BST 转换为累加树
  9.     root->val = sum;
  10.     traverse(root->left);
  11. }
  12. TreeNode* convertBST(TreeNode* root) {
  13.     traverse(root);
  15. }

BST 相关的题目，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目要求。