跳到主要内容

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

本节目标

用显式栈进行中序遍历，在访问第 K 个节点时立即返回。

这道题利用构造与二叉搜索树中的中序有序性，在找到目标后不再访问剩余节点。

查看 LeetCode 原题

题意与边界​

给定 BST 与有效的 k，返回按升序排列后的第 k 小节点值。单节点树且 k = 1 是最小边界；题目保证 k 不会超出节点数。

迭代中序早停​

中序遍历顺序是左、根、右，因此访问节点的值严格递增。指针持续沿左链入栈；到空节点后弹出栈顶并访问它，再转向其右子树。每弹出一个节点令 k 减一，减到零时该节点正是答案，可立即返回。

正确性依据​

栈始终保存尚未访问、但其左侧已经或正在被处理的祖先。每次弹出的节点是当前未访问节点中最小者；随后转向右子树不会遗漏更小值。故第 k 次弹出对应全树中第 k 小的值，早停不会影响答案。

代码实现​

C++17
#include <stack>

using namespace std;

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> nodes;
        TreeNode* cur = root;

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

            cur = nodes.top();
            nodes.pop();
            k--;
            if (k == 0) {
                return cur->val;
            }
            cur = cur->right;
        }

        return 0;
    }
};

复杂度分析​

最坏访问所有节点，时间复杂度为 O(n)；找到目标前实际访问 k 个节点及其左链。显式栈最多保存树高 h 个节点，额外空间为 O(h)。

易错点​

  • 把前序或后序当成有序访问，BST 只有中序遍历有递增性质。
  • 每次弹栈后忘记转向右子树，漏掉右侧节点。
  • 找到第 k 个节点后继续遍历，增加无用工作。

模式迁移​

当需要 BST 的第 K 大元素时，可改用右、根、左的逆中序；若查询频繁且树可修改，则可学习维护子树节点数的增强 BST。