这篇文章是关于「二叉搜索树 BST Binary Search Tree」的，目标是手把手刷BST。
BST的特性有两个：

对于BST的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 要大。
对于BST的每一个节点 node，它的左侧子树和右侧子树都是 BST。

从做算法题的角度上来看BST，除了上面两个特性，还有一个重要性质：BST的中序遍历结果是有序的（升序）。
因为BST的每一个节点的左子树都比当前节点的值要小，每一个节点的右子树节点的值都比当前节点要大，那么中序遍历（先遍历完左子树，然后加上根节点，再遍历完右子树）返回的就是升序的遍历结果了。

void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // 中序遍历代码位置
    print(root.val);
    traverse(root.right);
}

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

// 主函数
public int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return res;
}
// 记录结果
int res = 0;
// 记录当前元素的排名
int rank = 0;
// 定义：寻找以root为根的BST的第k小的元素
void traverse(TreeNode root, int k){
    if(root == null) return;
    traverse(root.left, k);
    // 中序遍历位置
    rank++;
    if(k == rank){
        // 找到第k小的元素（升序中第k个元素）
        res = root.val;
        return;
    }
    traverse(root.right, k);
}

这道题的解法，完全就是靠「BST的中序遍历结果是有序的」这一特性来做的。题目要我们求第k小的元素，那么中序遍历当前的BST，每次遇到一个节点rank就递增1，直到遇到第k个元素直接返回即可。

当然也可以把整个BST都遍历一遍，把每个节点值都保存起来，最后取第k个，也是可以的，但是时间复杂度上就慢很多。

public int kthSmallest(TreeNode root, int k) {
    traverse(root);
    return res.get(k-1);
}

LinkedList<Integer> res = new LinkedList<>();

// 定义：寻找以root为根的BST的第k小的元素
void traverse(TreeNode root){
    if(root == null) return;

    traverse(root.left);

    // 中序遍历位置
    res.add(root.val);

    traverse(root.right);
}

538. 把二叉搜索树转换为累加树

这道题跟 1038. 从二叉搜索树到更大和树这道题完全一样，可以一起做掉。

正确的解法很简单，还是利用 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 转化成累加树了吗？

// 主函数
public TreeNode convertBST(TreeNode root) {
    traverse(root);
    return root;
}

// 记录累加和
int sum = 0;

// 定义：逆序遍历BST，将每个节点的值更新为大于或等于当前节点的值的和
void traverse(TreeNode root){
    if(root == null) return;

    // 调换traverse(root.left) 和 traverse(root.left)的位置，从而实现倒序
    traverse(root.right);

    // 中序遍历位置
    // 维护累加和
    sum += root.val;
    // 将BST转化成累加树
    root.val = sum;

    traverse(root.left);
}

这道题的核心是，BST的中序遍历特性，只不过我们修改了递归顺序（通过调换traverse(root.left) 和 traverse(root.right) 就可以打印降序的节点值），降序遍历BST的元素值，从而契合题目累加树的要求。

总结

简单总结下吧，BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求，也就这么些事儿吧。

Leetcode刷题记录

特性篇(1038、230、538、剑指54)

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

538. 把二叉搜索树转换为累加树

总结