算法

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

loser

28 Aug 2026 • 10 min read

给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 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 <= 10^4
0 <= Node.val <= 10^4

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

解法一（递归中序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int count = 0;
    int ans = 0;

public:
    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return ans;
    }

private:
    void inorder(TreeNode* node, int k) {
        if (node == nullptr || count >= k)
        {
            return;
        }

        inorder(node->left, k);

        if (count >= k)
        {
            return;
        }

        ++count;
        if (count == k)
        {
            ans = node->val;
            return;
        }

        inorder(node->right, k);
    }
};

解法二（迭代中序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while (cur != nullptr || !st.empty())
        {
            while (cur != nullptr)
            {
                st.push(cur);
                cur = cur->left;
            }

            cur = st.top();
            st.pop();

            --k;
            if (k == 0)
            {
                return cur->val;
            }

            cur = cur->right;
        }

        return -1;
    }
};

核心思想

这题给的是二叉搜索树，而不是普通二叉树。

二叉搜索树最重要的性质是：

对二叉搜索树做中序遍历，得到的节点值序列一定是严格递增的。

因此，二叉搜索树中的第 k 小元素，就是中序遍历过程中第 k 个访问到的节点。

普通做法可以先把所有中序遍历结果放进数组，再返回数组下标 k - 1 的元素。

但这样会保存全部节点，其实没有必要。

只要在中序遍历过程中计数，当访问到第 k 个节点时，直接返回这个节点值即可。

为什么中序遍历能找到第 `k` 小

中序遍历顺序是：

左子树 -> 当前节点 -> 右子树

在二叉搜索树中：

左子树所有节点值都小于当前节点。
右子树所有节点值都大于当前节点。
左右子树自身也都是二叉搜索树。

所以先遍历左子树，会先得到所有比当前节点小的值。

然后访问当前节点。

最后遍历右子树，会得到所有比当前节点大的值。

这个顺序正好是从小到大。

因此，只需要数中序遍历访问到第几个节点。

第 k 个访问到的节点，就是第 k 小的元素。

解法一：递归中序遍历

递归函数 inorder(node, k) 表示：

按照中序顺序遍历以 node 为根的子树

访问顺序固定为：

inorder(node->left, k);
访问 node;
inorder(node->right, k);

代码中用 count 表示已经访问过多少个节点。

每访问到一个节点，就执行：

++count

如果：

count == k

说明当前节点就是第 k 个被中序遍历访问到的节点，也就是答案。

此时记录：

ans = node->val

解法二：迭代中序遍历

迭代写法用栈模拟递归。

栈中保存的是：

已经经过，但左子树还没完全处理完的节点

从根节点开始，不断沿着左孩子向下走，并把沿途节点压入栈：

st.push(cur);
cur = cur->left;

当 cur == nullptr 时，说明已经走到当前路径最左边。

这时栈顶节点就是当前应该访问的最小未访问节点。

弹出栈顶后，让 k 减一：

--k;

如果 k == 0，说明这个节点就是第 k 小的元素，直接返回。

否则继续处理它的右子树：

cur = cur->right;

迭代写法不依赖递归调用栈，遇到第 k 个节点就可以立刻结束，是这题常用的推荐写法。

为什么不能直接走左子树

看到“第 k 小”，容易想到一直往左走。

但一直往左只能找到整棵树的最小值，也就是第 1 小。

如果要找第 k 小，就需要知道：

左子树里有多少个节点。
当前节点是第几个。
是否应该去右子树继续找。

如果没有额外维护子树大小，就只能通过中序遍历按顺序计数。

所以普通场景下，中序遍历是最直接可靠的做法。

进阶优化：维护子树大小

如果二叉搜索树经常被插入或删除，并且需要频繁查询第 k 小，单次中序遍历的 O(n) 时间就不够理想。

可以在每个节点中额外维护一个字段：

size = 以当前节点为根的子树节点数

这样查找第 k 小时，先看左子树大小：

leftSize = size(root->left)

然后分三种情况：

如果 k <= leftSize，第 k 小在左子树中。
如果 k == leftSize + 1，当前节点就是第 k 小。
如果 k > leftSize + 1，第 k 小在右子树中，需要查找右子树中的第 k - leftSize - 1 小。

每次查询只会沿着树高向下走，所以时间复杂度是 O(h)。

其中 h 是树的高度。

插入或删除节点时，需要沿着修改路径更新祖先节点的 size。

如果这棵树是平衡二叉搜索树，那么 h = O(log n)，查询、插入和删除都可以做到 O(log n)。

这类结构也叫“带排名信息的二叉搜索树”或“顺序统计树”。

边界情况

如果 k = 1，答案就是二叉搜索树中的最小节点，也就是中序遍历访问到的第一个节点。

如果 k = n，答案就是二叉搜索树中的最大节点，也就是中序遍历访问到的最后一个节点。

如果树只有一个节点，那么 k 只能为 1，中序遍历第一次访问根节点时就返回它。

题目保证：

1 <= k <= n

所以一定存在第 k 小的节点。

题目中节点值满足 0 <= Node.val <= 10^4，不会影响中序遍历顺序。

正确性证明

我们证明：两个解法都能返回二叉搜索树中第 k 小的元素。

结论 1：二叉搜索树的中序遍历结果严格递增

对于任意一个节点，左子树中所有节点值都小于当前节点，右子树中所有节点值都大于当前节点。

同时，左右子树自身也都是二叉搜索树。

中序遍历会先访问左子树，再访问当前节点，最后访问右子树。

因此，左子树中的所有值会出现在当前节点之前，右子树中的所有值会出现在当前节点之后。

递归地看，整棵树的中序遍历结果就是严格递增序列。

结论 2：中序遍历中第 `k` 个访问到的节点就是第 `k` 小元素

由结论 1 可知，中序遍历结果按照节点值从小到大排列。

在一个严格递增序列中，第 k 个元素正好就是第 k 小的元素。

所以只要算法能找到中序遍历的第 k 个节点，就能得到正确答案。

结论 3：递归解法能找到中序遍历中的第 `k` 个节点

递归解法按照：

左子树 -> 当前节点 -> 右子树

的顺序访问节点。

每访问一个节点，count 增加 1。

因此，当 count == k 时，当前节点就是中序遍历中第 k 个访问到的节点。

算法把当前节点值记录到 ans 中。

所以递归解法能找到第 k 个中序节点。

结论 4：迭代解法能找到中序遍历中的第 `k` 个节点

迭代解法不断沿左子树下降，并用栈保存暂时不能访问的节点。

当不能继续向左时，弹出栈顶节点并访问它。

访问后再转向右子树。

这正是中序遍历顺序。

每访问一个节点，算法执行 --k。

当 k == 0 时，说明已经访问了原始意义上的第 k 个节点。

算法返回当前节点值。

所以迭代解法也能找到第 k 个中序节点。

得出结论

由结论 1 可知，二叉搜索树的中序遍历结果严格递增。

由结论 2 可知，中序遍历第 k 个节点就是第 k 小元素。

由结论 3 可知，递归解法能找到这个节点。

由结论 4 可知，迭代解法也能找到这个节点。

因此两个解法都能正确返回二叉搜索树中第 k 小的元素。

举例理解

以：

root = [5,3,6,2,4,null,null,1], k = 3

为例，这棵树可以理解为：

它的中序遍历顺序是：

1, 2, 3, 4, 5, 6

第 3 个访问到的节点是 3。

所以返回：

用迭代栈看过程：

当前动作	栈	`k`
压入 `5`，转向左子树	`[5]`	`3`
压入 `3`，转向左子树	`[5,3]`	`3`
压入 `2`，转向左子树	`[5,3,2]`	`3`
压入 `1`，转向左子树	`[5,3,2,1]`	`3`
弹出并访问 `1`	`[5,3,2]`	`2`
弹出并访问 `2`	`[5,3]`	`1`
弹出并访问 `3`	`[5]`	`0`

当 k 减到 0 时，当前节点值就是答案 3。

复杂度分析

设二叉搜索树节点数为 n，树的高度为 h。

解法一

最坏情况下，需要访问到最后一个节点。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点最多入栈一次、出栈一次，最坏情况下访问所有节点。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自显式维护的栈。

如果很早访问到第 k 个节点，迭代解法可以提前返回，不必遍历整棵树。

进阶优化

如果每个节点维护子树大小 size，查询第 k 小只需要沿树高向下走。

查询时间复杂度：O(h)
插入 / 删除更新时间复杂度：O(h)
额外空间复杂度：O(n)

如果使用平衡二叉搜索树，则 h = O(log n)，查询和修改都可以做到 O(log n)。