BST 第 K 小：中序走到第 k 个就停
二叉搜索树中序遍历严格升序。不必排序，也不必先列出全部：边走边数，第 k 次访问根，就是答案。
中序 DFS：先左、再访问当前节点并把 count 加一，count==k 时记下值并停止后续递归。左子树里的节点都比当前小，所以第 k 个被访问的就是第 k 小。平均 O(h+k)，最坏 O(n)，空间 O(h)。
给你一棵二叉搜索树的根和一个整数 k，返回树里第 k 小的元素。节点值互不相同。k 从 1 开始数。
主例层序 [3, 1, 4, null, 2]，k=1。树是 3 为根，左 1（1 的右孩子是 2），右 4。中序走出来是 1、2、3、4。第 1 小是 1，也就是最左边那个节点。k=3 才会走到根 3。
把节点倒进数组再下标 k−1 能做对，但多走了后面那些更大的节点。本文要回答：为什么中序的第 k 次「访问」就是第 k 小，以及主例 k=1 时为什么左子树一到底就可以返回。
中序第 k 个
BST 的定义给出一句能用的话：任意节点，左子树都比它小，右子树都比它大。因此中序——先左、再自己、再右——得到的序列严格递增。第 k 小不是「再排序一次」，就是这条序列上的第 k 项。缺的只是一个计数器：访问到一个节点就 +1，加到 k 停。
递归写成：若节点空，或 count 已经达到 k，直接返回。先 dfs 左子树。回来后 count++；若 count==k，记下当前值，再返回，不再走右子树。否则 dfs 右子树。count>=k 的守卫让已经找到答案之后，沿途的栈只做返回，不再访问新节点。
用手走主例，k=1。从 3 进左子树 1。1 的左孩子空，于是访问 1，count 从 0 变成 1，等于 k，记下 1，右孩子 2 不再进入。回到 3 时 count 已经是 1，守卫挡住，4 也不会走。演示场景只标出访问 1、命中，对应这一次短路。
若 k=3：访问 1 时 count=1，继续走 1 的右孩子 2，count=2；回到 3，count=3，命中 3，4 仍不用走。中序序列的前缀 1、2、3 正好是从小到大的前三个。把 BST 当成普通二叉树层序找第 k 个，主例会先碰到 3，错成「第 1 小是 3」。
最左叶子是第 1 小，最右叶子是第 n 小。求第 k 大可以中序倒着走，或者求第 n−k+1 小。若节点上额外存了子树规模，可以比较 k 和左子树大小，决定向左还是向右，平均变成 O(h)；本题不假设有这个额外字段，老老实实中序计数即可。
中序有序BST 是唯一能保证「中序 = 升序」的二叉树。第 k 小、验证 BST、后继前驱，用的都是这句话。普通二叉树的中序没有大小含义。
Go：中序计数
func kthSmallest(root *TreeNode, k int) int {count, result := 0, 0var dfs func(*TreeNode)dfs = func(n *TreeNode) {if n == nil || count >= k { return }dfs(n.Left)count++if count == k { result = n.Val; return }dfs(n.Right)}dfs(root)return result}
1count 已经到 k 就不再往下走。主例记下 1 之后，2、3、4 都被这行挡住。
2先左。左子树里的节点都更小，会先被数到。
3访问当前节点才 +1。count==k 时的 n.Val 就是第 k 小。
4没满 k 再走右。k=3 时会经过 1、2，在 3 上命中。
总结
BST 中序即升序，数到第 k 个节点停。主例 k=1 就是最左的 1。
- 层序第 k 个不是第 k 小。主例层序第一个是 3，中序第一个是 1。
- count>=k 剪掉右子树和祖先的剩余工作。
- 第 k 大 = 中序倒序第 k 个，或正序第 n−k+1 个。