DeepSeek LeetCode 230. 二叉搜索树中第 K 小的元素 Java实现

LeetCode 230. 二叉搜索树中第 K 小的元素 Java 实现

思路：中序遍历（迭代）

二叉搜索树（BST）的中序遍历结果是严格升序的。
因此，中序遍历时访问到的第 k 个节点，就是第 k 小的元素。

使用栈模拟中序遍历，可以边走边计数，找到第 k 个立即返回，无需遍历完整棵树。

Java 代码

import java.util.*;

class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;

while (cur != null || !stack.isEmpty()) {
// 一路向左，把路径上的节点压栈
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 弹出栈顶，即当前最小节点
cur = stack.pop();
if (—k == 0) {
return cur.val;
}
// 转向右子树
cur = cur.right;
}

return –1; // 题目保证 k 有效，不会执行到这里
}
}

复杂度分析

· 时间复杂度：O(H + k)，其中 H 为树高。最坏情况 O(n)。
· 空间复杂度：O(H)，栈的深度为树高。最坏 O(n)。

示例

// 树结构：
// 3
// / \\
// 1 4
// \\
// 2

root = [3,1,4,null,2]
k = 1 → 1
k = 2 → 2
k = 3 → 3
k = 4 → 4

关键点

· BST 中序遍历 = 升序序列。
· 迭代中序用 Deque 做栈，先左到底，再弹出计数，最后走右子树。
· 找到第 k 个直接返回，不需要继续遍历。
· 若追求 O(1) 空间，可使用 Morris 中序遍历，但代码较复杂，面试中迭代法已足够。

附：递归写法（简洁）

class Solution {
private int count = 0;
private int result = –1;

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

private void inorder(TreeNode node, int k) {
if (node == null) return;
inorder(node.left, k);
if (++count == k) {
result = node.val;
return;
}
inorder(node.right, k);
}
}

递归写法同样 O(H + k) 时间、O(H) 空间，但需要成员变量记录状态。