Frontend Interview

Appearance

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

题目链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

代码 ​

ts
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function kthSmallest(root: TreeNode | null, k: number): number {
    let res = 0;
    function dfs(node: TreeNode | null): void {
        if (!node || k <= 0) return;
        dfs(node.left); // 中序遍历
        if(--k === 0){
            res = node.val;
        }
        dfs(node.right);
    }
    dfs(root);
    return res;
};

思路 ​

利用二叉搜索树的中序遍历是有序序列的性质：

  1. 对 BST 进行中序遍历（左 → 根 → 右）
  2. 遍历过程中递减计数器 k
  3. 当 k 减到 0 时，当前节点就是第 k 小的元素
  4. 使用闭包变量 res 保存结果

关键点 ​

  • BST 的中序遍历结果是升序排列的

  • 不需要遍历完整棵树，找到第 k 个元素后可以提前终止

  • 使用 k <= 0 作为递归终止条件，避免不必要的遍历

  • 在访问节点时先 --k，然后判断是否为 0

  • 时间复杂度 O(H+k)，其中 H 是树的高度，最坏情况下需要遍历 k 个节点

  • 空间复杂度 O(H)，递归调用栈的深度