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

难度：🟡 Medium | 标签：树、BST | 状态：⬜ LeetCode 链接

思路

BST 中序遍历是升序。中序到第 k 个就是答案。 迭代版栈走中序，计数到 k 即返回。

代码

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        auto* cur = root;
        while (cur || !st.empty()) {
            while (cur) { st.push(cur); cur = cur->left; }
            cur = st.top(); st.pop();
            if (--k == 0) return cur->val;
            cur = cur->right;
        }
        return -1;
    }
};

复杂度

• 时间 O(h + k)，空间 O(h)

易错 / 回顾

• 不要中序到底再 res[k-1]——浪费 O(n)
• 进阶（频繁查询）：节点维护子树大小，O(h) 查询
• --k 在弹出之后再判