中序遍历BST可直接得第K小元素，因其天然升序；需用引用参数记录访问数并提前终止，避免全树遍历；递归或迭代均应处理空树、k越界等边界情况。
为什么中序遍历能直接拿到第K小元素
二叉搜索树（BST）的中序遍历天然产生升序序列，所以第K小元素就是中序遍历过程中访问到的第K个节点。不需要先建数组再取索引，更不用排序——这是BST结构本身赋予的性质。
关键点在于：不能只写一个返回值的递归函数（比如 int inorder(TreeNode*)），因为需要同时传递「当前已访问多少个节点」和「是否已找到结果」两个状态。常见错误是强行用全局变量或忽略提前终止，导致遍历整棵树，浪费时间。
- 推荐用引用参数记录已访问节点数：
int& count - 一旦
count == k，立刻通过返回值或额外参数把结果带出来，不再深入右子树 - 空节点必须返回，且不改变
count
递归实现中如何安全提前返回
标准中序递归框架是「左→根→右」，但第K小可能在左子树就找到了，也可能在根，也可能在右子树。如果左子树返回了有效值，就该跳过根和右子树；如果左子树没找到，才检查根；根也不满足，才进右子树。
示例逻辑（C++）：
立即学习“C++免费学习笔记（深入）”；
int kthSmallest(TreeNode* root, int k) {
int count = 0;
return dfs(root, k, count);
}
<p>int dfs(TreeNode* node, int k, int& count) {
if (!node) return -1; // 假设节点值非负，-1 表示未找到</p><pre class="brush:php;toolbar:false;">int left = dfs(node->left, k, count);
if (left != -1) return left; // 左子树已找到
count++;
if (count == k) return node->val;
return dfs(node->right, k, count); // 右子树继续找}
注意：这里用 -1 作哨兵值，前提是题目保证节点值为正整数；否则应改用 std::optional<int></int> 或额外布尔引用参数。
迭代方式避免递归栈溢出
当树深度很大（比如退化成链表），递归容易栈溢出。迭代用显式栈模拟中序遍历，同样边走边计数，找到第K个就停。
核心是「一路向左压栈，弹出时计数，再转向右子树」：
- 每次从栈弹出一个节点，
count++ - 若
count == k，直接返回该节点值 - 否则将该节点的右子树所有左链节点压入栈（即模拟「进入右子树后先一路向左」）
常见错误：压右子树时漏掉「压完整左链」，只压了右孩子本身，导致跳过中间节点。
K值越界或树为空怎么处理
题目通常保证 1 ≤ k ≤ size，但实际工程中必须考虑边界。比如 k == 0、root == nullptr、k 大于总节点数。
建议统一返回一个可判别的值（如抛出异常或返回 std::nullopt），而不是硬写 return 0 —— 因为 0 可能是合法节点值。
如果用迭代法，可在开始前加一次节点总数统计（O(n)），但会多一遍遍历；更轻量的做法是在遍历中检测「栈空且无新节点可入」时仍没找到，说明K越界。
真正容易被忽略的是：BST定义只保证左
