二叉搜索树(Binary Search Tree, BST)是特殊的二叉树，它满足如下性质：

• 左小右大：对于BST的每一个节点，它左子树节点的值都小于根节点的值，右子树节点的值都大于根节点的值。
• 递归定义：对于BST的每一个节点，它的左子树和右子树也都是BST。
• 中序升序：BST的中序遍历结果是升序的。

直接基于BST的数据结构有AVL树、红黑树等，拥有自平衡性质；还有B+树，线段树等结构都是基于BST的思想来设计的。因此学好BST也很重要。

中序升序

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

可以利用中序遍历来找：

int ans = 0;
int rank = 0;

void traverse(TreeNode* root, int k)
{
    if (root)
    {
        traverse(root->left, k);
        rank++;
        if (rank == k)
        {
            ans = root->val;
            return;
        }
        traverse(root->right, k);
    }
}

int kthSmallest(TreeNode* root, int k) {
    traverse(root, k);
    return ans;
}

如果可以自定义BST节点，那么可以新增一个size成员，它表示以自己为根的BST节点数。然后配合左子树根节点和右子树根节点的size，就能确认当前的排名。确认排名后，便可进行“剪枝”操作，往目标排名处搜索。

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

我们可以通过倒序的中序遍历（右中左）的方式来解决这道题，只需这样遍历一次，维护每个节点的累加和就好了：

int sum = 0;

void traverse(TreeNode* root)
{
    if (root)
    {
        traverse(root->right);
        sum += root->val;
        root->val = sum;
        traverse(root->left);
    }
}

TreeNode* convertBST(TreeNode* root) {
    traverse(root);
    return root;
}

类似题目：

• 1038. 从二叉搜索树到更大和树 - 力扣（LeetCode）

增删改查

利用BST左小右大的特性，可以快速查找到目标节点。BST的遍历框架如下：

void traverseBST(TreeNode* root, int target)
{
    if (root)
    {
        if (root->val == target)
        {
            // 找到了, 做点什么
        }
        else if (root->val > target)
            traverseBST(root->left, target);
        else
            traverseBST(root->right, target);
    }
    
}

判断BST合法性

98. 验证二叉搜索树 - 力扣（LeetCode）

有时候要根据BST“左小右大”的特性来判断BST合法性，可以这样写：

bool traverse(TreeNode* root, long minVal, long maxVal)
{
    if (root)
    {
        if (root->val <= minVal)    return false;
        if (root->val >= maxVal)    return false;

        return traverse(root->left, minVal, root->val) && traverse(root->right, root->val, maxVal);
    }
    return true;
}

bool isValidBST(TreeNode* root) {
    return traverse(root, numeric_limits<long>::lowest(), numeric_limits<long>::max());
}

这里由于树节点是int类型，最大值最小值使用long。

插入一个数

可以使用BST的遍历框架，找到符合条件的空节点位置，然后在这里插入：

TreeNode* insertBST(TreeNode* root, int val)
{
    // 找到空节点位置
    if (root == nullptr)
        return new TreeNode(val);
    else
    {
        if (root->val > val)
            root->left = insertBST(root->left, val);
        else if (root->val < val)
            root->right = insertBST(root->right, val);
        else
            return root;
    }
}

删除一个数

要删除一个数，首先得先找到它，用traverseBST()框架找到这个节点。找到后该如何删除呢，得分情况讨论：

• 要删除的节点是叶子节点，那么它可以被直接删除。
• 要删除的节点只有一个孩子节点，那么让该孩子节点接替自己的位置。
• 要删除的节点有两个孩子节点，有两种选择：找到左子树中最大的节点，然后替换自己；找到右子树中最小的节点，然后替换自己。

代码如下：

TreeNode* deleteBST(TreeNode* root, int target)
{
    if (root == nullptr)	return nullptr;
    if (root->val == target)
    {
        // 情况1和2
        if (root->left == nullptr)	
            return root->right;
        if (root->right == nullptr)
           	return root->left;
       	
        // 情况3: 这里找右子树最小节点, 然后替换
        TreeNode* minNode = root->right;
        while (minNode->left)
            minNode = minNode->left;
        // 删除右子树最小节点
        root->right = deleteBST(root->right, minNode->val);
        // 然后用最小节点替换root节点
        minNode->left = root->left;
        minNode->right = root->right;
        root = minNode;
    }
    else if (root->val > target)
        root->left = deleteBST(root->left, target);
    else if (root->val < target)
        root->right = deleteBST(root->right, target);
    return root;
}