AlgoViz Lab交互式算法学习
Algorithms first

二叉搜索树中第 K 小的元素 · 交互式算法学习

返回 BST 中第 k 小的元素。

#230 · 二叉搜索树

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

Kth Smallest Element in a BST

测试用例root = [3,1,4,null,2], k = 1
树 / 图3 个关键状态
步骤 1把 3、1 压入左链栈。stack=[3,1]
3142
推荐

迭代中序提前停止

时间 O(h+k)空间 O(h)

左链入栈，每弹出一个节点就把 k 减一，减到零立即返回。

1function kthSmallest(root, k) {2  const s = [];3  while (true) {4    while (root) {5      s.push(root);6      root = root.left7    }8    root = s.pop();9    if (--k === 0) return root.val;10    root = root.right;11  }12}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int kthSmallest(TreeNode root, int k) {18        Deque<TreeNode> stk = new ArrayDeque<>();19        while (root != null || !stk.isEmpty()) {20            if (root != null) {21                stk.push(root);22                root = root.left;23            } else {24                root = stk.pop();25                if (--k == 0) {26                    return root.val;27                }28                root = root.right;29            }30        }31        return 0;32    }33}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

二叉搜索树中第 K 小的元素 · 解法对比

AlgoViz Lab

返回 BST 中第 k 小的元素。

测试用例
root = [3,1,4,null,2], k = 1
题目分类
二叉搜索树
解法对比
2
方案 1

完整中序数组

中序遍历生成升序数组，读取 k-1。

时间
O(n)
空间
O(n)
方案 2

迭代中序提前停止

左链入栈，每弹出一个节点就把 k 减一，减到零立即返回。

时间
O(h+k)
空间
O(h)