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`` 只是为了满足编译器的完整返回路径,
合法题目输入不会走到该分支;节点值范围保证它不会与合法答案混淆。