Kth Smallest Element in a BST（二叉搜索树中第 K 小的元素）
题目 / Problem
中文： 给定一棵二叉搜索树的根节点 root 和一个整数 k，返回树中所有节点值的第 k 小元素。k 从 1 开始计数。
English: Given the root of a binary search tree and an integer k, return the kth smallest value among all node values. k is 1-indexed.
示例 / Examples
Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
中序遍历结果为 [1,2,3,4]，第 1 个元素是 1。
The inorder traversal is [1,2,3,4], whose first element is 1.
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
中序遍历结果为 [1,2,3,4,5,6]，第 3 个元素是 3。
The inorder traversal is [1,2,3,4,5,6], whose third element is 3.
约束 / Constraints
- 树中节点数量为
n。
The tree containsnnodes. 1 <= k <= n <= 10^40 <= Node.val <= 10^4
核心性质：BST 的中序遍历有序 / Key Property: BST Inorder Is Sorted
二叉搜索树满足：
A binary search tree satisfies:
左子树节点值 < 根节点值 < 右子树节点值
left-subtree values < root value < right-subtree values
中序遍历的访问顺序是：
Inorder traversal visits nodes in this order:
左子树 → 根节点 → 右子树
Left subtree → Root → Right subtree
因此，对 BST 进行中序遍历会按从小到大的顺序访问节点。第 k 个访问到的节点就是第 k 小元素。
Therefore, inorder traversal of a BST visits values from smallest to largest. The kth visited node is the kth smallest value.
解题思路：迭代中序遍历 / Approach: Iterative Inorder Traversal
使用栈模拟递归中序遍历：
Use a stack to simulate recursive inorder traversal:
- 从当前节点不断向左移动，并将沿途节点压入栈。
Move left repeatedly, pushing every visited node onto the stack. - 无法继续向左时，弹出栈顶节点。
When no further left move is possible, pop the top node. - 该节点是当前尚未访问节点中的最小值，计数加一。
This node is the smallest unvisited value, so increment the visit count. - 如果计数等于
k，直接返回该节点值。
If the count equalsk, return the node's value immediately. - 否则转向该节点的右子树，重复以上过程。
Otherwise, move to its right subtree and repeat.
算法不需要生成完整的有序数组，找到第 k 个节点后即可提前停止。
There is no need to construct the complete sorted array; stop as soon as the kth node is reached.
栈的作用 / Role of the Stack
栈保存“已经到达但还不能访问”的祖先节点：
The stack stores ancestors that have been reached but cannot yet be visited:
5
/
3
/
2
/
1
向左下降后的栈 / Stack after descending left:
[5, 3, 2, 1]
弹出顺序从最左节点开始，因此符合中序遍历的升序要求。
Popping begins with the leftmost node, preserving the ascending inorder order.
JavaScript 实现 / JavaScript Implementation
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = val ?? 0;
* this.left = left ?? null;
* this.right = right ?? null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
function kthSmallest(root, k) {
const stack = [];
let current = root;
let visited = 0;
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
visited++;
if (visited === k) {
return current.val;
}
current = current.right;
}
// 题目保证 1 <= k <= 节点数量，因此不会执行到这里。
// Constraints guarantee a valid k, so this line is unreachable.
return -1;
}
执行过程 / Walkthrough
使用 Example 2：
Using Example 2:
5
/ \
3 6
/ \
2 4
/
1
中序访问过程：
Inorder visits:
| 访问次序 / Visit | 节点值 / Value | 是否达到 k = 3 / Reached k? |
|---|---|---|
| 1 | 1 | 否 / No |
| 2 | 2 | 否 / No |
| 3 | 3 | 是 / Yes，返回 3 / return 3 |
节点 4、5 和 6 不需要继续访问。
Nodes 4, 5, and 6 do not need to be visited.
递归写法 / Recursive Version
也可以使用递归中序遍历，并在找到答案后停止继续搜索：
A recursive inorder traversal can also stop after finding the answer:
function kthSmallest(root, k) {
let remaining = k;
let answer = -1;
function inorder(node) {
if (node === null || remaining === 0) {
return;
}
inorder(node.left);
if (remaining === 0) {
return;
}
remaining--;
if (remaining === 0) {
answer = node.val;
return;
}
inorder(node.right);
}
inorder(root);
return answer;
}
迭代版本不会受到 JavaScript 递归调用栈深度的限制，更适合可能严重偏斜的树。
The iterative version avoids JavaScript recursion-depth limits and is safer for highly skewed trees.
进阶：频繁修改和查询 / Follow-up: Frequent Updates and Queries
如果 BST 经常进行插入、删除，并且频繁查询第 k 小元素，可以为每个节点维护：
If the BST is frequently updated and queried, augment every node with:
subtreeSize = 以当前节点为根的子树节点数量
number of nodes in the current node's subtree
查询时，设左子树大小为 leftSize：
During a query, let leftSize be the size of the left subtree:
- 如果
k === leftSize + 1，当前节点就是答案。
Ifk === leftSize + 1, the current node is the answer. - 如果
k <= leftSize，答案位于左子树。
Ifk <= leftSize, search the left subtree. - 如果
k > leftSize + 1，答案位于右子树，并令k -= leftSize + 1。
Ifk > leftSize + 1, search the right subtree withk -= leftSize + 1.
function kthSmallestWithSize(root, k) {
let current = root;
while (current !== null) {
const leftSize = current.left?.subtreeSize ?? 0;
if (k === leftSize + 1) {
return current.val;
}
if (k <= leftSize) {
current = current.left;
} else {
k -= leftSize + 1;
current = current.right;
}
}
return -1;
}
插入或删除节点时，需要沿搜索路径更新所有祖先节点的 subtreeSize。
When inserting or deleting a node, update subtreeSize for every ancestor along the search path.
如果使用 AVL 树、红黑树等平衡 BST，并维护子树大小：
With a balanced BST such as an AVL or red-black tree augmented with subtree sizes:
- 插入 / Insert:
O(log n) - 删除 / Delete:
O(log n) - 查询第
k小 / Kth-smallest query:O(log n)
这种结构也称为顺序统计树（Order Statistic Tree）。
This augmented structure is also called an Order Statistic Tree.
复杂度 / Complexity
设树高为 h。
Let h be the tree height.
- 时间复杂度 / Time:
O(h + k)，遍历到第k个节点后停止；最坏为O(n)。O(h + k)before stopping at thekth node;O(n)in the worst case. - 空间复杂度 / Space:
O(h)，用于显式栈。O(h)for the explicit stack.
平衡树中 h = O(log n)，完全偏斜的树中 h = O(n)。
For a balanced tree, h = O(log n); for a completely skewed tree, h = O(n).
易错点 / Common Pitfalls
k从1开始计数，不是从0开始。kis 1-indexed, not 0-indexed.- 必须使用中序遍历“左 → 根 → 右”，不能使用前序或后序遍历。
Use inorder traversal left-root-right, not preorder or postorder. - 找到第
k个节点后可以立即返回，不需要遍历完整棵树。
Return immediately after reaching thekth node; do not traverse the whole tree unnecessarily. - 迭代写法的外层条件是
current !== null || stack.length > 0。
The iterative outer condition iscurrent !== null || stack.length > 0. - 从栈中弹出节点并访问后，应转向它的右子树。
After popping and visiting a node, move to its right subtree. - 进阶方案中，插入、删除和树旋转后都必须正确维护
subtreeSize。
In the augmented solution, maintainsubtreeSizeafter insertions, deletions, and tree rotations.