企业官网建设流程全解析

1. 这道题到底在考什么

先说结论：LeetCode 230 不是一道难题，但它是一道极好的“二叉树基础检阅题”。题目本身只有一句话，给定一棵二叉搜索树（BST）和一个整数 k，返回第 k 小的元素。很多人第一次拿到这题会直接愣住——又是“第 K 小”又是“树”，感觉像要排序又要遍历，搞不清优先级。

实际上这道题考察的东西非常明确：你是否理解二叉搜索树的顺序性质，以及你能否把“树的遍历”和“有序序列”联系起来。一句话，它考的是中序遍历。因为二叉搜索树的左子树节点值都小于根节点，右子树节点值都大于根节点，所以对它做一次左-根-右的中序遍历，得到的序列天然就是从小到大排列的。那么第 K 小，说白了就是中序遍历后第 K 个输出的节点。

这道题适合谁刷？我建议刚把二叉树遍历搞明白、准备系统性刷树的同学把它当作入门必刷题。它的解法层级很清楚：先有一个最笨但最不容易出错的“完整中序遍历收集法”，再有一个效率更高的“中序遍历提前终止法”，最后还有一个应对高频查询的进阶思路。由浅入深，一题能带出三种算法思想，性价比极高。面试中如果你能把三种写法都讲清楚，面试官对你的评价会明显不一样。

2. 核心思路拆解：为什么中序遍历是突破口

2.1 二叉搜索树的一个隐藏规律

很多人刷题时会把二叉树当成一种“链表+分治”的混合体来硬记，其实二叉搜索树最大的特点就是有序性内嵌在结构里。对于任意一个节点，它的左子树所有节点都比它小，右子树所有节点都比它大，而且这个性质对树里的每一个子树都成立。

这就带来一个非常实用的推论：中序遍历BST，得到的就是有序数组。左子树先输出，然后当前节点，再右子树，整个过程正好符合“小-中-大”的顺序。我第一次意识到这一点时，觉得这东西跟二分查找简直是天生一对——你完全可以用“有序数组”的思维去处理二叉搜索树的问题。

再往深了说，这个性质还意味着：如果你要给一棵 BST 做“查找第 K 小”“查找某个值是否存在”“找上下界”之类的操作，根本不需要把整棵树展开成数组，你可以沿着树的路径定向搜索，把时间从 O(n) 压缩到 O(height)。230 题虽然最简单的方式就是中序遍历，但它的进阶解法恰恰是利用了这个定向搜索的思路。

2.2 四种解法的全景对比

这道题我见过的解法大致分四类，每一层的思路角度都不同：

如果你只是应付这道题本身，第二、三种足够了。但如果你想把二叉树的基础打牢，我建议四种都过一遍。尤其是第四种思路，它牵扯到一个很重要的设计思想：“用额外的空间维护索引信息，换取高频查询的效率”，这在真实工程里非常常见，像数据库索引、跳表、平衡树都是这个套路。

3. 解法一：最朴素的中序遍历收集法

3.1 完整代码与执行流程

先上一个最简单的版本。思路是：反正中序遍历得到的就是有序数组，那我不如直接把整棵树“拍扁”成数组，然后取第 k-1 个元素。这里注意题目给的 k 是从 1 开始计数的，所以数组下标要减一。

class Solution { public int kthSmallest(TreeNode root, int k) { List<Integer> list = new ArrayList<>(); inorder(root, list); return list.get(k - 1); } private void inorder(TreeNode node, List<Integer> list) { if (node == null) { return; } inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }

这个代码非常简单，我来演示一下它在一棵具体树上的执行过程。假设树的结构是这样：

5 / \ 3 6 / \ 2 4 / 1

中序遍历的递归顺序是：一直往左走，走到节点 1，访问它，然后回溯到 2，访问 2，再到 3，访问 3，再到 4，访问 4，最后右边 5、6。最终 list 里的内容是 [1, 2, 3, 4, 5, 6]。如果 k=3，那就返回 list.get(2)，也就是 3。

3.2 这个解法的问题在哪里

收集法最大的优点就是逻辑清晰、不容易写错，特别适合在面试最开始用来破题——你先把最简单的方法讲出来，证明你理解了题目的本质，然后再逐步优化。但它有两个明显的性能问题。

第一个问题是空间浪费。为了找一个数，你把整棵树都存进了数组，空间复杂度从 O(height) 变成了 O(n)。如果这棵树特别大，比如有上百万个节点，这个数组会白白占用大量内存。第二个问题是做了很多无用功。如果 k=2，理论上遍历到第二个节点就能停了，但收集法非要把整棵树都遍历完才肯罢休。

所以这个版本我会把它定位成“热身解法”。面试时如果只写这一版，面试官大概率会追问一句：能不能不遍历完整棵树？这就自然过渡到下面要讲的提前终止法了。

4. 解法二：中序遍历+计数器提前终止

4.1 用栈模拟递归的迭代写法

提前终止的难点在于：如果用递归写，你很难在找到答案后立刻“跳出”整个递归过程。虽然可以用一个全局变量或者返回值来做标记，但代码写起来总是变扭。所以更优雅的方式是改成迭代式的中序遍历，用一个显式的栈来模拟递归的调用过程，这样遍历到第 k 个节点时直接 return，干净利落。

class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; int count = 0; while (cur != null || !stack.isEmpty()) { // 先把左子树一路压栈 while (cur != null) { stack.push(cur); cur = cur.left; } // 弹出一个节点，相当于“访问” cur = stack.pop(); count++; if (count == k) { return cur.val; } // 转向右子树 cur = cur.right; } return -1; // 理论上不会走到这里 } }

我拆解一下这个迭代中序遍历的节奏。外层 while 循环的条件是“当前节点不为空 或 栈不为空”。只要还有节点要处理，循环就不停。内层 while 负责把当前节点的所有左子树节点压入栈中，这对应了递归里的“先走到最左边”。然后弹出栈顶元素，它就是当前子树里最小的未访问节点，count 加一，如果等于 k 就说明找到了。最后把 cur 指向弹出节点的右孩子，下一轮循环就会去处理右子树。整个过程用手在纸上画一遍会非常清晰。

4.2 为什么这个版本是面试最优解

相比收集法，这个版本的时间和空间都更优。时间复杂度上，它最多遍历 k 个节点就停下，最坏情况下 k=n 才遍历完整棵树，所以是 O(k)，相比收集法的固定 O(n) 有提升。空间复杂度上，栈中最多存储树高个节点，对于一棵相对平衡的树来说是 O(log n)，极端退化链状树则退化为 O(n)，但无论如何不会像收集法那样存所有节点。

面试里我建议你优先写这个版本。它同时考察了你三个能力：是否理解中序遍历的本质、是否掌握用栈模拟递归、是否懂得通过计数提前终止。写完之后你可以主动补充一句：“如果这棵树不会变，而且要频繁查第 K 小，我还可以给每个节点记录子树大小，这样查询能降到 O(log n)。”这句话一说出来，面试官基本就知道你对这个知识点的理解到位了。

注意：在 Java 里，官方推荐的栈写法是ArrayDeque而不是Stack。Stack继承自Vector，所有方法都加了锁，性能差且已经被官方标记为建议不用。LeetCode 上虽然能通过，但工程里没人这么写。

4.3 如果题目要求反过来，求第 K 大呢

这是一个非常高频的追问变体。其实思路完全一样，只需要把中序遍历的顺序改成“右-根-左”，因为这样遍历得到的就是降序数列，第 k 个输出的就是第 k 大。代码几乎不用改，把入栈顺序调换一下：

class Solution { public int kthLargest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; int count = 0; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.right; // 注意这里变成了右 } cur = stack.pop(); count++; if (count == k) { return cur.val; } cur = cur.left; // 注意这里变成了左 } return -1; } }

5. 解法三：如果节点能记录子树大小，把查询降为 O(log n)

5.1 思路来源：把树当作二分查找的载体

如果你刷过“二叉搜索树中查找某个数是否存在”这类题，你会发现递归查找的每一步都像二分：目标比当前节点小就往左走，比当前节点大就往右走。既然 BST 天然支持“定点查找”，那“找第 K 小”为什么不能像二分一样直接定向？答案是可以，但前提是你要知道以每个节点为根的子树里一共有多少个节点。

假设每个节点都额外存储了一个字段size，表示以它为根的子树的节点总数。那么站在根节点，左子树的 size 就代表“比根节点小的节点有多少个”，这个信息决定了第 k 小在什么位置：

• 如果左子树的 size 大于等于 k，说明第 k 小在左子树里，往左走。
• 如果左子树的 size 刚好等于 k-1，说明比根节点小的有 k-1 个，那根节点就是第 k 小。
• 否则，第 k 小在右子树里，并且要更新 k 为k - leftSize - 1，把左子树加根节点这些已经排除掉的节点数减掉。

这个过程有点像在一本按字母排序的字典里翻页：你看了左边半本有多厚，就知道目标词在不在那里面，不用一页一页翻。

5.2 子树节点数怎么维护

麻烦的地方在于：LeetCode 默认给你的TreeNode结构里没有size字段，你不能直接改它的定义。所以这个解法要分场景讨论。如果是在刷题环境里，你可以自定义一个带 size 的树节点，或者先做一次后序遍历统计出每个子树的大小存到 HashMap 里。我把后序遍历统计的版本写出来：

class Solution { private Map<TreeNode, Integer> sizeMap = new HashMap<>(); public int kthSmallest(TreeNode root, int k) { computeSize(root); return search(root, k); } private int computeSize(TreeNode node) { if (node == null) { return 0; } int left = computeSize(node.left); int right = computeSize(node.right); int size = left + right + 1; sizeMap.put(node, size); return size; } private int search(TreeNode node, int k) { if (node == null) { return -1; } int leftSize = sizeMap.getOrDefault(node.left, 0); if (leftSize >= k) { return search(node.left, k); } else if (leftSize + 1 == k) { return node.val; } else { return search(node.right, k - leftSize - 1); } } }

这个版本的查询时间复杂度是 O(height)，也就是 O(log n)（平衡树情况下）。但注意，computeSize本身需要 O(n) 的时间。所以它的优势不在“一次查询”，而在“多次查询”。如果在工程中你需要对一个不会频繁增删的 BST 做大量“第 K 小”查询，你完全可以在构建树的时候顺便维护好 size，把每次查询压到对数级。这其实就是一个很经典的“空间换时间”设计思路。

6. 常见错误与刷题避坑实录

6.1 递归中提前终止的“失控”问题

如果你非要用递归写提前终止版本，很容易踩一个坑：递归函数已经返回正确答案了，但外层调用还在继续执行。比如这样写：

class Solution { int count = 0; int ans = -1; public int kthSmallest(TreeNode root, int k) { inorder(root, k); return ans; } private void inorder(TreeNode node, int k) { if (node == null || ans != -1) return; // 找到答案后剪枝 inorder(node.left, k); count++; if (count == k) { ans = node.val; return; } inorder(node.right, k); } }

这段代码虽然能跑对，但它依赖全局变量来传递状态，一旦你忘记在递归入口重置全局变量（LeetCode 每次执行对象是同一个实例），就可能出现上次运行残留的 count 或 ans，导致这次结果错误。我在实际刷题时就吃过这个亏，调试了半天才发现是全局变量没复位。建议是：能在方法内解决的就不放全局，或者封装成内部类来传递状态。

6.2 对 k 的边界理解出错

题目说 k 是从 1 开始计的，但数组索引是从 0 开始，所以收集法取list.get(k - 1)而不是list.get(k)。这个错误很隐蔽，我第一次写就错了。迭代法里用 count 从 0 开始计数，弹出节点后先count++再比较是否等于 k，逻辑上更不容易搞错边界。如果你写成先比较后加一，就变成“第 k+1 小”了。

6.3 空指针和退化树的处理

测试用例不会给你空树，但你别自己把代码写崩。在迭代版本里，如果一棵树退化成了链状结构，比如每个节点只有左孩子没有右孩子，栈的深度会达到 n，空间复杂度退化为 O(n)。虽然 LeetCode 的数据不会卡这个，但面试时最好主动提一句这个问题，说明你有考虑最坏情况。

还有一个细节：sizeMap.getOrDefault(node.left, 0)这行代码非常关键。如果左子树是 null，sizeMap里没有它的键，直接 get 会返回 null，导致 int 拆箱 NullPointerException。用getOrDefault一句话就规避了。这种报错在 LeetCode 上不会每次出现，只有当树结构恰好缺了某一侧子树时才触发，隐蔽性很强。

7. 同类题扩展与刷题顺序建议

7.1 做完 230 之后应该接着刷什么

这道题做完，我强烈建议你趁热打铁刷下面几道题，它们用的是同一套中序遍历思维：

• LeetCode 94 二叉树的中序遍历：基础中的基础，迭代和递归都要会，230 的迭代解法完全基于它。
• LeetCode 173 二叉搜索树迭代器：把中序遍历拆成next()和hasNext()，本质上就是 230 的迭代版。这题还会引出“扁平化”思想，很有意思。
• LeetCode 98 验证二叉搜索树：用中序遍历判断序列是否严格递增，和 230 的数组收集法异曲同工。
• LeetCode 285 二叉搜索树中的中序后继：如果你明白了中序遍历顺序，这题就是找“下一个输出的节点是谁”。
• LeetCode 538 把二叉搜索树转换为累加树：反向中序遍历（右-根-左）的练习题，顺便练了第 K 大的变体。

这几道题全部做完，你对“中序遍历”的理解会从“会写代码”上升到“会灵活换序”。我个人觉得这是二叉树刷题里性价比最高的一个系列。

7.2 LeetCode 刷题的一个小习惯

聊点题外话。我见过很多人刷题只看题解从不自己推演，结果刷了三百题还是没思路。230 这道题特别适合用来练“手推过程”——拿笔在纸上画一棵树，用手动模拟栈的 push 和 pop，把整个中序遍历的走向一步步走通。你把这个过程走通了，比抄十遍题解都有用，因为你会真的理解“为什么这个写法是对的”。

另外一定要给自己定一个复盘周期。我自己的习惯是：一道题 AC 之后，隔 3 天不看代码重新写一遍，写不出来就说明没真懂。230 这种基础题尤其值得多写几遍，写到闭着眼睛都能敲出来的程度，面试时你会非常有底气。

8. 一点个人的实战心得

最后分享一个我自己的体会：像 230 这种基础题，刷它的价值不在于“通过”，而在于“能不能在一分钟内讲清楚思路”。我曾经在模拟面试时被要求现场讲这题，第一次我直接说“用中序遍历”，面试官接着问“为什么中序遍历就行”，我卡了两秒才反应过来要强调 BST 的有序性。就这两秒，印象分就降了半档。

所以我的建议是：每做完一道题，用一句话把解法核心写在这道题的备注里，比如 230 的备注就是“BST 中序遍历即升序，迭代栈实现可提前终止”。下次看到这道题先回忆这句话，再展开细节。长期积累下来，你会发现自己对算法的理解比单纯刷题量要深得多。

如果你把这道题吃透了，后面遇到“BST 的第 K 大”、工程里的 Top K 问题、甚至数据库里 B+ 树的区间查询，都会有那种“原来都是同一套路”的豁然感。这就是刷基础题最值得的地方。