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

怎样从“这题不是让我们排序数组，而是让我们在一棵二叉搜索树里找第 k 小的节点；关键是 BST 本身已经隐含了大小关系。”推导出 BST · 第 K 小，并证明每次状态变化都不会漏掉答案？

中心结论：BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

在本站主例中，这题不是让我们排序数组，而是让我们在一棵二叉搜索树里找第 k 小的节点；关键是 BST 本身已经隐含了大小关系。

算法最终需要得到或观察：中序序列 [1,2,3,4,5,6]，k=3，答案为 3。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 cur、stack、k 倒计时、visited 访问序列。
3. 3转移每一步按照 BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。
4. 4收尾读取 中序序列 [1,2,3,4,5,6]，k=3，答案为 3。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：cur、stack、k 倒计时、visited 访问序列。

由于二叉搜索树有序的特性，所以中根遍历它，遍历到第 K 个数的时候就是结果

BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。

执行过程中持续维护：cur、stack、k 倒计时、visited 访问序列。

正确性依赖以下不变量：BST 左子树所有节点都比当前节点小，右子树所有节点都比当前节点大。；中序遍历顺序是左子树、当前节点、右子树。；所以 BST 的中序遍历结果就是从小到大的序列。

面试时可以压缩为：利用 BST 的性质：左子树小于根，右子树大于根，所以 BST 中序遍历升序。遍历时计数，到第 k 个节点立即返回。递归和显式栈都可以，时间平均 O(k)、最坏 O(n)，空间 O(h)。

落到当前题，执行机制可以压缩为：BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入这题不是让我们排序数组，而是让我们在一棵二叉搜索树里找第 k 小的节点；关键是 BST 本身已经隐含了大小关系。 因为：BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。
2. 2沿左子树压栈,cur=0左边界全部入栈。 因为：最后处理的才是最左结点。
3. 3沿左子树压栈,cur=3左边界全部入栈。 因为：最后处理的才是最左结点。
4. 4弹出并访问 1访问结点,转向右子树。 因为：左子树已全部处理完。
5. 5沿左子树压栈,cur=4左边界全部入栈。 因为：最后处理的才是最左结点。
6. 6弹出并访问 5访问结点,转向右子树。 因为：左子树已全部处理完。
7. 7弹出并访问 undefined访问结点,转向右子树。 因为：左子树已全部处理完。
8. 8收尾与复杂度中序序列 [1,2,3,4,5,6]，k=3，答案为 3。 因为：时间 O(k) 平均，最坏 O(n) · 空间 O(h)。BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func kthSmallest(root *TreeNode, k int) int {
	res, count := 0, 0
	inorder(root, k, &count, &res)
	return res
}

func inorder(node *TreeNode, k int, count *int, ans *int) {
	if node != nil {
		inorder(node.Left, k, count, ans)
		*count++
		if *count == k {
			*ans = node.Val
			return
		}
		inorder(node.Right, k, count, ans)
	}
}

func main() {
    // 1. 主例
    //    输入：mode="inorder", values=[5,3,6,2,4,null,null,1], target=3
    //    期望：中序序列 [1,2,3,4,5,6]，k=3，答案为 3。
    //
    // 2. 失败 / 未命中
    //    检查：k 从 1 计数别从 0。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC700 搜索；LC98 验证
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意这题不是让我们排序数组，而是让我们在一棵二叉搜索树里找第 k 小的节点；关键是 BST 本身已经隐含了大小关系。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化BST 的中序遍历天然升序；递归或显式栈模拟左-根-右，访问节点时让 k 倒计时，k==0 返回当前节点。
4. 4证明BST 左子树所有节点都比当前节点小，右子树所有节点都比当前节点大。；中序遍历顺序是左子树、当前节点、右子树。；所以 BST 的中序遍历结果就是从小到大的序列。
5. 5复杂度时间 O(k) 平均，最坏 O(n)，空间 O(h)