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

一、题目

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

二、题解

方法一：递归中序遍历

思路：中序遍历 / DFS / 二叉搜索树

1. 核心思路

二叉搜索树有一个非常重要的性质：

左子树所有节点 < 根节点 < 右子树所有节点

所以对二叉搜索树进行 中序遍历：

左子树 -> 根节点 -> 右子树

得到的结果一定是升序的。

因此：

中序遍历访问到的第 1 个节点，就是第 1 小的元素
中序遍历访问到的第 2 个节点，就是第 2 小的元素
中序遍历访问到的第 k 个节点，就是第 k 小的元素

核心思想是：

  • 利用 BST 中序遍历结果有序的特点；
  • 每访问一个节点，就让 k 减 1；
  • 当 k == 0 时，当前节点就是第 k 小的元素。

2. 具体步骤

  1. 使用中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
  2. 定义变量 count 记录还需要访问几个节点。
  3. 每访问一个节点，就让 count--。
  4. 当 count == 0 时，说明当前节点就是第 k 小的元素。
  5. 用变量 result 保存答案。

3. 关键逻辑

count--;

if (count == 0) {
    result = root.val;
    return;
}

解释：

  • 每访问一个节点，说明当前节点是升序序列中的一个元素；
  • count-- 表示还需要往后找的节点数量减少了一个；
  • 当 count == 0 时，当前节点正好是第 k 小的元素。

4. 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // 还需要访问几个节点
    private int count;

    // 保存最终答案
    private int result;

    public int kthSmallest(TreeNode root, int k) {
        // 1. 初始化 count
        count = k;

        // 2. 中序遍历
        inorder(root);

        // 3. 返回答案
        return result;
    }

    // 中序遍历：左 -> 根 -> 右
    private void inorder(TreeNode root) {
        // 如果节点为空，直接返回
        // 如果 count == 0，说明已经找到答案，也可以提前返回
        if (root == null || count == 0) {
            return;
        }

        // 1. 先遍历左子树
        inorder(root.left);

        // 2. 访问当前节点
        count--;

        // 如果 count == 0，当前节点就是第 k 小的元素
        if (count == 0) {
            result = root.val;
            return;
        }

        // 3. 最后遍历右子树
        inorder(root.right);
    }
}

5. 复杂度分析

时间复杂度：O(H+k)O(H + k)

说明：

H 是树的高度。

因为中序遍历时，会先沿着左子树走到底，这部分最多需要 H 次操作。

之后访问节点，直到找到第 k 小的元素为止，所以最多再访问 k 个节点。

因此时间复杂度是 O(H+k)O(H + k)。

如果最坏情况下需要遍历整棵树，时间复杂度是 O(n)O(n)。

空间复杂度：O(H)O(H)

说明：

递归调用栈的深度最多等于树的高度。

如果是平衡二叉树，空间复杂度是 O(log⁡n)O(\log n)。

如果是链状二叉树，空间复杂度是 O(n)O(n)。

方法二：迭代中序遍历

思路：栈 / 中序遍历 / 二叉搜索树

1. 核心思路

方法一使用递归完成中序遍历。

方法二使用栈手动模拟递归过程。

中序遍历的顺序是：

左 -> 根 -> 右

为了先访问最小的节点，需要不断向左走，并把沿途节点压入栈中。

当不能继续向左时，弹出栈顶节点，这个节点就是当前还没有访问过的最小节点。

这种方法的核心是：

  • 用栈保存从根节点到当前节点路径上的节点；
  • 一直向左走，找到当前最小节点；
  • 每弹出一个节点，就表示访问了升序序列中的一个元素；
  • 当访问到第 k 个节点时，直接返回它的值。

2. 具体步骤

  1. 创建一个栈 stack。
  2. 当前节点不为空时，一直向左走，并把节点压入栈中。
  3. 当左边走到底后，从栈中弹出一个节点。
  4. 弹出的节点就是当前应该访问的节点。
  5. 每访问一个节点，让 k--。
  6. 如果 k == 0，返回当前节点的值。
  7. 然后继续遍历当前节点的右子树。

3. 关键逻辑

while (root != null) {
    stack.push(root);
    root = root.left;
}

root = stack.pop();
k--;

if (k == 0) {
    return root.val;
}

root = root.right;

解释：

  • while (root != null) 是为了不断找到更小的左节点；
  • stack.pop() 弹出的节点，就是当前升序序列中下一个节点；
  • k-- 表示已经访问了一个节点；
  • 当 k == 0，当前节点就是第 k 小的元素；
  • 最后转向右子树，继续寻找后面的节点。

4. 代码

import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // 1. 定义栈，用来模拟递归
        Stack<TreeNode> stack = new Stack<>();

        // 2. 中序遍历
        while (root != null || !stack.isEmpty()) {

            // 3. 一直向左走，把沿途节点压入栈中
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // 4. 弹出栈顶节点，相当于访问当前节点
            root = stack.pop();

            // 5. 已经访问了一个节点，k 减 1
            k--;

            // 6. 如果 k == 0，说明当前节点就是第 k 小的元素
            if (k == 0) {
                return root.val;
            }

            // 7. 继续遍历右子树
            root = root.right;
        }

        // 正常情况下不会走到这里，因为题目保证 k 是有效的
        return -1;
    }
}

5. 复杂度分析

时间复杂度：O(H+k)O(H + k)

说明：

H 是树的高度。

迭代过程中，先向左走到底，需要最多 H 次操作。

之后每弹出一个节点，就访问一个元素，直到访问到第 k 个节点为止。

因此时间复杂度是 O(H+k)O(H + k)。

最坏情况下需要遍历所有节点，时间复杂度是 O(n)O(n)。

空间复杂度：O(H)O(H)

说明：

栈中最多保存从根节点到叶子节点的一条路径。

如果是平衡二叉树，空间复杂度是 O(log⁡n)O(\log n)。

如果是链状二叉树，空间复杂度是 O(n)O(n)。

评论