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

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：二叉搜索树 (BST)、中序遍历

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

示例 1：

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

示例 2：

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

---

2. 解题思路拆解

核心性质：二叉搜索树的 中序遍历 (Left -> Root -> Right) 是一个 升序序列。

因此，我们要找第 k 小的元素，只需要对二叉搜索树进行中序遍历，并计数。

• 访问第 1 个节点：第 1 小。
• 访问第 2 个节点：第 2 小。
• ...
• 访问第 k 个节点：第 k 小，直接返回该节点的值。

方法一：递归中序遍历

我们可以维护一个全局计数器 count，或者在递归参数中传递。 当 count === k 时，记录结果并停止遍历（或者直接返回）。

方法二：迭代中序遍历 (栈)

使用栈模拟中序遍历，控制流更清晰。

1. 一路向左入栈。
2. 弹出节点，计数器 k--。
3. 如果 k === 0，返回当前节点值。
4. 转向右子树。

---

3. 代码实现

迭代法 (推荐，逻辑清晰)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    const stack = [];
    let curr = root;
    
    while (curr !== null || stack.length > 0) {
        // 1. 一路向左
        while (curr !== null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        // 2. 弹出节点
        curr = stack.pop();
        k--; // 找到第 1 小、第 2 小...
        
        // 3. 检查是否是第 k 小
        if (k === 0) {
            return curr.val;
        }
        
        // 4. 转向右子树
        curr = curr.right;
    }
    
    return -1; // 理论上不会走到这里
};

递归法

var kthSmallest = function(root, k) {
    let res = null;
    let count = 0;
    
    const inorder = (node) => {
        if (!node || res !== null) return; // 剪枝：如果已经找到了，直接返回
        
        inorder(node.left);
        
        count++;
        if (count === k) {
            res = node.val;
            return;
        }
        
        inorder(node.right);
    };
    
    inorder(root);
    return res;
};

代码执行演示 (迭代法)

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

    5
   / \
  3   6
 / \
2   4
/
1

1. Push 5, 3, 2, 1. Stack: [5, 3, 2, 1].
2. Pop 1. k=2. Right null.
3. Pop 2. k=1. Right null.
4. Pop 3. k=0. Return 3.

---

4. 复杂度分析

维度	描述
时间复杂度	$O(H + k)$。$H$ 是树高。我们需要先走到最左下的节点（$O(H)$），然后遍历 $k$ 个节点。
空间复杂度	$O(H)$。栈的深度。