0230. Kth Smallest Element in a BST =================================== 题目信息 -------- :题号: 0230 :难度: Medium :主题: 二叉搜索树、中序遍历、顺序统计 :原题: `LeetCode 0230 `_ :重点: BST 严格有序、k 从 1 开始、返回节点值、节点保证存在 题目重述 -------- 给定一棵二叉搜索树的根节点 ``root`` 和整数 ``k``,返回树中第 ``k`` 小的节点值。这里 ``k`` 使用一基排名:``k=1`` 表示最小值,``k`` 等于节点数时表示最大值。 树中节点数位于 ``[1, 10^4]``,``1 <= k <= 节点数``,节点值位于 ``[0, 10^4]``。输入保证是合法二叉搜索树,节点值互不相同,并保证第 ``k`` 小元素一定存在。函数返回对应的整数值,不修改树。题目的进阶问题考虑树经常插入、删除且需要频繁查询时的设计。 自建示例 -------- 查询中间排名: .. code-block:: text 输入:root = [6, 3, 9, 1, 4, 8, 11],k = 4 输出:6 解释:节点值按升序排列为 [1, 3, 4, 6, 8, 9, 11],第 4 小的值是 6。 查询最大值: .. code-block:: text 输入:root = [2, 1, 5, null, null, 4, 7],k = 5 输出:7 解释:树共有 5 个节点,第 5 小就是最大节点值 7。 中序遍历就是升序序列 -------------------- 二叉搜索树满足左子树所有值小于当前节点、右子树所有值大于当前节点,因此中序顺序 ``左子树 -> 当前节点 -> 右子树`` 会依次访问第 1 小、第 2 小直到最大值。 不必把完整中序序列保存下来:用栈模拟递归,先把当前节点及其左链压栈;弹出一个节点时, 它就是下一个最小值,递减 ``k``,若 ``k`` 变为 0 立即返回,否则转向它的右子树。 正确性说明 ---------- 栈中从栈顶到栈底保存的是尚未访问节点中最靠左的一条路径。每次弹出的节点都没有未访问的左后继, 且它的所有左侧节点已经先被弹出;进入右子树后,再按同样规则访问其左侧节点,所以弹出顺序严格等于 BST 的中序序列。 第 ``k`` 次弹出的节点因此就是第 ``k`` 小节点,题目保证该节点存在。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int kthSmallest(TreeNode* root, int k) { std::stack nodes; TreeNode* current = root; while (current != nullptr || !nodes.empty()) { while (current != nullptr) { nodes.push(current); current = current->left; } current = nodes.top(); nodes.pop(); if (--k == 0) return current->val; current = current->right; } return -1; } }; 代码分析 -------- 算法只访问到第 ``k`` 个节点及其必要的左链;最坏情况下仍会访问整棵树,时间复杂度为 ``O(n)``, 递归等价的栈空间为 ``O(h)``,其中 ``h`` 是树高。返回 ``-1`` 只是为了满足编译器的完整返回路径, 合法题目输入不会走到该分支;节点值范围保证它不会与合法答案混淆。