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

描述

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

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

1. 迭代法

先来看一种非递归的方法，中序遍历最先遍历到的是最小的结点，只要用一个计数器，每遍历一个结点，计数器自增1，当计数器到达k时，返回当前结点值即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        // 定义一个栈，用于迭代遍历二叉搜索树
        stack<TreeNode*> s;
        // 定义一个指针，指向当前节点
        TreeNode* p = root;
        // 计数器，记录已经遍历过的节点数
        int count = 0;
        // 当栈不为空或者当前节点不为空时循环
        while (!s.empty() || p != nullptr) {
            // 遍历左子树
            while (p != nullptr) {
                s.push(p);
                p = p->left;
            }
            // 弹出栈顶元素
            p = s.top();
            s.pop();
            // 计数器加一
            count++;
            // 如果计数器等于 k，返回当前节点的值
            if (count == k) {
                return p->val;
            }
            // 遍历右子树
            p = p->right;
        }
        // 如果找不到第 k 小的元素，返回 -1
        return -1;
    }
};

2. 递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        // 计算左子树的节点数
        int leftCount = countNodes(root->left);
        // 如果左子树的节点数等于 k-1，返回根节点的值
        if (leftCount == k - 1) {
            return root->val;
        }
        // 如果左子树的节点数大于等于 k，递归遍历左子树
        else if (leftCount >= k) {
            return kthSmallest(root->left, k);
        }
        // 如果左子树的节点数小于 k-1，递归遍历右子树
        else {
            return kthSmallest(root->right, k - leftCount - 1);
        }
    }

    // 计算以 root 为根节点的子树的节点数
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};