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

本文概览：本文以LeetCode题目"二叉搜索树中第K小的元素"为例，讲解如何利用BST中序遍历递增的性质，通过全局计数器在遍历过程中找到第K小的元素，并用-1作为标识实现找到即退出

一、题目

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

二、题目分析

这道题和上一篇"验证二叉搜索树"是同一个思路来的。由于是二叉搜索树，中序遍历的结果就是递增序列，所以中序遍历到第 k 个元素，就是第 K 小的元素

思路是通用的，但这个中序遍历需要多加点东西了：

全局计数器：必须知道当前遍历到第几个元素了，所以需要一个计数器 count，用属性记录就好了，这个是对象方法内全局统一的
找到即退出：当计数器到达 k 时，说明找到了目标元素，应该直接退出，不再继续遍历后面的节点

思路概览

Java 实现代码如下

class Solution {
    private int count = 0;

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

    private int getKthSmallest(TreeNode root, int k) {
        // 中序遍历
        if (root == null) {
            return -1;
        }

        // 左子树
        int left = getKthSmallest(root.left, k);
        // 左子树有k个节点，直接返回
        if (left != -1) {
            return left;
        }
        // 当前节点
        count++;
        // 当前节点是第k个节点，直接返回
        if (count == k) {
            return root.val;
        }
        // 右子树
        int right = getKthSmallest(root.right, k);
        // 右子树有k个节点，直接返回
        if (right != -1) {
            return right;
        }
        // 没有第k个节点，返回-1
        return -1;
    }
}

思路简要说明

在中序遍历的基础上，增加一个全局计数器 count，每遍历一个节点就 count++
用 -1 作为标识：如果返回 -1，说明这个节点不是最终值，继续遍历；只有 count == k 时才返回 root.val（非 -1）
左子树遍历完后检查返回值，如果不是 -1，说明左子树已经找到答案，直接返回，不再处理当前节点和右子树

三、思路详解

中序遍历的递增性质

这和上一篇"验证二叉搜索树"是同一个起点：BST 的中序遍历（左→根→右）一定是严格递增的

        5
       / \
      3   6
     / \   \
    2   4   7

中序遍历：2 → 3 → 4 → 5 → 6 → 7

第1小=2, 第2小=3, 第3小=4, 第4小=5...

所以找第 K 小的元素，就是中序遍历到第 k 个元素时返回它的值

两个要解决的问题

普通的中序遍历只是"遍历所有节点"，但这道题有两个额外要求：

1. 需要计数——知道遍历到第几个了

每遍历到一个节点，计数器 count 加 1。用类的属性 count 来记录，这样在整个递归过程中是全局统一的，所有递归调用共享同一个计数器

2. 找到即退出——不要白干活

当 count == k 时，说明当前节点就是第 K 小的元素，直接返回它的值。不需要再继续遍历后面的节点了

-1 标识的设计

这里用 -1 作为"没找到"的标识：

返回 -1：说明这个节点（及其子树）里没有找到第 K 小的元素，调用方应该继续往别处找
返回非 -1：说明找到了第 K 小的元素，直接层层返回，不再继续遍历

为什么能这样设计？因为题目保证树中至少有 k 个节点，所以最终一定会找到。-1 只是一个中间状态的标识，表示"这条路还没找到"

代码执行流程

以这棵树为例，找第 3 小的元素（k=3）：

        5
       / \
      3   6
     / \   \
    2   4   7

中序遍历：2 → 3 → 4 → 5 → 6 → 7
第3小 = 4

逐层看递归过程：

调用 getKthSmallest(5, 3)
  → 调用 getKthSmallest(3, 3)    // 先走左子树
    → 调用 getKthSmallest(2, 3)  // 先走左子树
      → 调用 getKthSmallest(null, 3) → 返回 -1
      左子树返回 -1，继续
      count++ → count=1，1 != 3，不是目标
      → 调用 getKthSmallest(null, 3) → 返回 -1
      右子树返回 -1，继续
      返回 -1                     // 节点2不是目标
    左子树返回 -1，继续
    count++ → count=2，2 != 3，不是目标
    → 调用 getKthSmallest(4, 3)  // 走右子树
      → 调用 getKthSmallest(null, 3) → 返回 -1
      左子树返回 -1，继续
      count++ → count=3，3 == 3！返回 4  ← 找到了！
    右子树返回 4（非-1），直接返回 4
  左子树返回 4（非-1），直接返回 4
最终返回 4

可以看到，一旦在节点 4 处 count == k，返回值 4 就会层层传递回去，每一层都因为 left != -1 或 right != -1 直接返回，不再继续遍历。节点 5、6、7 都没有被访问到——这就是"找到即退出"的效果

递归结构回顾

和普通中序遍历的结构对比：

	普通中序遍历	本题
出口	`if (root == null) return;`	`if (root == null) return -1;`
左子树	`inorder(root.left, res);`	`int left = ...; if (left != -1) return left;`
当前节点	`res.add(root.val);`	`count++; if (count == k) return root.val;`
右子树	`inorder(root.right, res);`	`int right = ...; if (right != -1) return right;`
返回值	无（void）	int（-1 或 root.val）