🔗 二叉搜索树中第 k 小的元素

题目来源：230. 二叉搜索树中第 K 小的元素 – 力扣（LeetCode）

---

📌 题目描述

给定一个二叉搜索树（BST）的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

---

✅ 示例解析

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

解释：中序遍历序列为 [1, 2, 3, 4]，第 1 小的元素是 1。

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

解释：中序遍历序列为 [1, 2, 3, 4, 5, 6]，第 3 小的元素是 3。

---

⚠️ 提示

• 树中的节点数为 n。
• 1 <= k <= n <= 10⁴
• 0 <= Node.val <= 10⁴

---

💡 解法：中序遍历（DFS 递归）—— O(H + k) 时间，O(H) 空间

class Solution {
    private int count = 0;       
    private int kthSmallest = 0;  

    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root, k);
        return kthSmallest;
    }

    private void inorderTraversal(TreeNode node, int k) {
        // 提前终止：节点为空，或已找到结果（可优化为 count >= k）
        if (node == null || count >= k) {
            return;
        }

        // 遍历左子树
        inorderTraversal(node.left, k);

        // 访问当前节点
        count++;
        if (count == k) {
            kthSmallest = node.val;
            return; // 找到后立即返回，避免无效遍历
        }

        // 遍历右子树
        inorderTraversal(node.right, k);
    }
}

✅ 优化说明：将终止条件从 count > k 改为 count >= k，并在找到结果后 return，可提前结束递归，提升效率。

---

📊 复杂度分析

• 时间复杂度：O(H + k)
  其中 H 是树的高度。最坏情况下需遍历 k 个节点（如左偏树），而到达第一个叶子需 H 步。
  • 平衡 BST：H = O(log n) → 总时间 O(log n + k)
  • 退化为链表：H = O(n) → 最坏 O(n)
• 空间复杂度：O(H)
  递归调用栈的深度等于树的高度 H。
  • 平衡树：O(log n)
  • 链表：O(n)

---

🧩 解题思路

核心性质：二叉搜索树的中序遍历是升序序列

• 中序遍历顺序：左子树 → 根节点 → 右子树
• 对 BST 而言，该顺序恰好是从小到大排列的节点值。

算法步骤：

1. 从根节点开始，递归进行中序遍历。
2. 每访问一个节点，计数器 count 加 1。
3. 当 count == k 时，当前节点值即为第 k 小的元素。
4. 关键优化：一旦找到目标，立即终止后续遍历，避免无意义操作。

为什么不能用层序或前序遍历？

• 只有中序遍历能保证 BST 节点值按升序访问，其他遍历无法直接定位第 k 小。