尧图网站建设 
1. 这道题到底在考什么先说结论LeetCode 230 不是一道难题但它是一道极好的“二叉树基础检阅题”。题目本身只有一句话给定一棵二叉搜索树BST和一个整数 k返回第 k 小的元素。很多人第一次拿到这题会直接愣住——又是“第 K 小”又是“树”感觉像要排序又要遍历搞不清优先级。实际上这道题考察的东西非常明确你是否理解二叉搜索树的顺序性质以及你能否把“树的遍历”和“有序序列”联系起来。一句话它考的是中序遍历。因为二叉搜索树的左子树节点值都小于根节点右子树节点值都大于根节点所以对它做一次左-根-右的中序遍历得到的序列天然就是从小到大排列的。那么第 K 小说白了就是中序遍历后第 K 个输出的节点。这道题适合谁刷我建议刚把二叉树遍历搞明白、准备系统性刷树的同学把它当作入门必刷题。它的解法层级很清楚先有一个最笨但最不容易出错的“完整中序遍历收集法”再有一个效率更高的“中序遍历提前终止法”最后还有一个应对高频查询的进阶思路。由浅入深一题能带出三种算法思想性价比极高。面试中如果你能把三种写法都讲清楚面试官对你的评价会明显不一样。2. 核心思路拆解为什么中序遍历是突破口2.1 二叉搜索树的一个隐藏规律很多人刷题时会把二叉树当成一种“链表分治”的混合体来硬记其实二叉搜索树最大的特点就是有序性内嵌在结构里。对于任意一个节点它的左子树所有节点都比它小右子树所有节点都比它大而且这个性质对树里的每一个子树都成立。这就带来一个非常实用的推论中序遍历BST得到的就是有序数组。左子树先输出然后当前节点再右子树整个过程正好符合“小-中-大”的顺序。我第一次意识到这一点时觉得这东西跟二分查找简直是天生一对——你完全可以用“有序数组”的思维去处理二叉搜索树的问题。再往深了说这个性质还意味着如果你要给一棵 BST 做“查找第 K 小”“查找某个值是否存在”“找上下界”之类的操作根本不需要把整棵树展开成数组你可以沿着树的路径定向搜索把时间从 O(n) 压缩到 O(height)。230 题虽然最简单的方式就是中序遍历但它的进阶解法恰恰是利用了这个定向搜索的思路。2.2 四种解法的全景对比这道题我见过的解法大致分四类每一层的思路角度都不同解法核心思路时间复杂度空间复杂度适用场景中序遍历收集遍历整棵树存入数组取下标 k-1O(n)O(n)思路直观适合新手理解中序遍历计数提前终止遍历时计数数到 k 就返回O(k)最坏 O(n)O(height)笔试面试最推荐递归剪枝/二分计数根据左子树节点数量判断目标在哪边O(height)O(height)掌握了之后写起来最优雅改造树结构记录子树大小每个节点维护子树节点数定向查找O(height)O(1) 额外频繁查询第 K 小的工程场景如果你只是应付这道题本身第二、三种足够了。但如果你想把二叉树的基础打牢我建议四种都过一遍。尤其是第四种思路它牵扯到一个很重要的设计思想“用额外的空间维护索引信息换取高频查询的效率”这在真实工程里非常常见像数据库索引、跳表、平衡树都是这个套路。3. 解法一最朴素的中序遍历收集法3.1 完整代码与执行流程先上一个最简单的版本。思路是反正中序遍历得到的就是有序数组那我不如直接把整棵树“拍扁”成数组然后取第 k-1 个元素。这里注意题目给的 k 是从 1 开始计数的所以数组下标要减一。class Solution { public int kthSmallest(TreeNode root, int k) { ListInteger list new ArrayList(); inorder(root, list); return list.get(k - 1); } private void inorder(TreeNode node, ListInteger 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]。如果 k3那就返回 list.get(2)也就是 3。3.2 这个解法的问题在哪里收集法最大的优点就是逻辑清晰、不容易写错特别适合在面试最开始用来破题——你先把最简单的方法讲出来证明你理解了题目的本质然后再逐步优化。但它有两个明显的性能问题。第一个问题是空间浪费。为了找一个数你把整棵树都存进了数组空间复杂度从 O(height) 变成了 O(n)。如果这棵树特别大比如有上百万个节点这个数组会白白占用大量内存。第二个问题是做了很多无用功。如果 k2理论上遍历到第二个节点就能停了但收集法非要把整棵树都遍历完才肯罢休。所以这个版本我会把它定位成“热身解法”。面试时如果只写这一版面试官大概率会追问一句能不能不遍历完整棵树这就自然过渡到下面要讲的提前终止法了。4. 解法二中序遍历计数器提前终止4.1 用栈模拟递归的迭代写法提前终止的难点在于如果用递归写你很难在找到答案后立刻“跳出”整个递归过程。虽然可以用一个全局变量或者返回值来做标记但代码写起来总是变扭。所以更优雅的方式是改成迭代式的中序遍历用一个显式的栈来模拟递归的调用过程这样遍历到第 k 个节点时直接 return干净利落。class Solution { public int kthSmallest(TreeNode root, int k) { DequeTreeNode 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 个节点就停下最坏情况下 kn 才遍历完整棵树所以是 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) { DequeTreeNode 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 MapTreeNode, 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逻辑上更不容易搞错边界。如果你写成先比较后加一就变成“第 k1 小”了。6.3 空指针和退化树的处理测试用例不会给你空树但你别自己把代码写崩。在迭代版本里如果一棵树退化成了链状结构比如每个节点只有左孩子没有右孩子栈的深度会达到 n空间复杂度退化为 O(n)。虽然 LeetCode 的数据不会卡这个但面试时最好主动提一句这个问题说明你有考虑最坏情况。还有一个细节sizeMap.getOrDefault(node.left, 0)这行代码非常关键。如果左子树是 nullsizeMap里没有它的键直接 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 树的区间查询都会有那种“原来都是同一套路”的豁然感。这就是刷基础题最值得的地方。 LeetCode 230 详解：二叉搜索树中序遍历求第K小元素
1. 这道题到底在考什么先说结论LeetCode 230 不是一道难题但它是一道极好的“二叉树基础检阅题”。题目本身只有一句话给定一棵二叉搜索树BST和一个整数 k返回第 k 小的元素。很多人第一次拿到这题会直接愣住——又是“第 K 小”又是“树”感觉像要排序又要遍历搞不清优先级。实际上这道题考察的东西非常明确你是否理解二叉搜索树的顺序性质以及你能否把“树的遍历”和“有序序列”联系起来。一句话它考的是中序遍历。因为二叉搜索树的左子树节点值都小于根节点右子树节点值都大于根节点所以对它做一次左-根-右的中序遍历得到的序列天然就是从小到大排列的。那么第 K 小说白了就是中序遍历后第 K 个输出的节点。这道题适合谁刷我建议刚把二叉树遍历搞明白、准备系统性刷树的同学把它当作入门必刷题。它的解法层级很清楚先有一个最笨但最不容易出错的“完整中序遍历收集法”再有一个效率更高的“中序遍历提前终止法”最后还有一个应对高频查询的进阶思路。由浅入深一题能带出三种算法思想性价比极高。面试中如果你能把三种写法都讲清楚面试官对你的评价会明显不一样。2. 核心思路拆解为什么中序遍历是突破口2.1 二叉搜索树的一个隐藏规律很多人刷题时会把二叉树当成一种“链表分治”的混合体来硬记其实二叉搜索树最大的特点就是有序性内嵌在结构里。对于任意一个节点它的左子树所有节点都比它小右子树所有节点都比它大而且这个性质对树里的每一个子树都成立。这就带来一个非常实用的推论中序遍历BST得到的就是有序数组。左子树先输出然后当前节点再右子树整个过程正好符合“小-中-大”的顺序。我第一次意识到这一点时觉得这东西跟二分查找简直是天生一对——你完全可以用“有序数组”的思维去处理二叉搜索树的问题。再往深了说这个性质还意味着如果你要给一棵 BST 做“查找第 K 小”“查找某个值是否存在”“找上下界”之类的操作根本不需要把整棵树展开成数组你可以沿着树的路径定向搜索把时间从 O(n) 压缩到 O(height)。230 题虽然最简单的方式就是中序遍历但它的进阶解法恰恰是利用了这个定向搜索的思路。2.2 四种解法的全景对比这道题我见过的解法大致分四类每一层的思路角度都不同解法核心思路时间复杂度空间复杂度适用场景中序遍历收集遍历整棵树存入数组取下标 k-1O(n)O(n)思路直观适合新手理解中序遍历计数提前终止遍历时计数数到 k 就返回O(k)最坏 O(n)O(height)笔试面试最推荐递归剪枝/二分计数根据左子树节点数量判断目标在哪边O(height)O(height)掌握了之后写起来最优雅改造树结构记录子树大小每个节点维护子树节点数定向查找O(height)O(1) 额外频繁查询第 K 小的工程场景如果你只是应付这道题本身第二、三种足够了。但如果你想把二叉树的基础打牢我建议四种都过一遍。尤其是第四种思路它牵扯到一个很重要的设计思想“用额外的空间维护索引信息换取高频查询的效率”这在真实工程里非常常见像数据库索引、跳表、平衡树都是这个套路。3. 解法一最朴素的中序遍历收集法3.1 完整代码与执行流程先上一个最简单的版本。思路是反正中序遍历得到的就是有序数组那我不如直接把整棵树“拍扁”成数组然后取第 k-1 个元素。这里注意题目给的 k 是从 1 开始计数的所以数组下标要减一。class Solution { public int kthSmallest(TreeNode root, int k) { ListInteger list new ArrayList(); inorder(root, list); return list.get(k - 1); } private void inorder(TreeNode node, ListInteger 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]。如果 k3那就返回 list.get(2)也就是 3。3.2 这个解法的问题在哪里收集法最大的优点就是逻辑清晰、不容易写错特别适合在面试最开始用来破题——你先把最简单的方法讲出来证明你理解了题目的本质然后再逐步优化。但它有两个明显的性能问题。第一个问题是空间浪费。为了找一个数你把整棵树都存进了数组空间复杂度从 O(height) 变成了 O(n)。如果这棵树特别大比如有上百万个节点这个数组会白白占用大量内存。第二个问题是做了很多无用功。如果 k2理论上遍历到第二个节点就能停了但收集法非要把整棵树都遍历完才肯罢休。所以这个版本我会把它定位成“热身解法”。面试时如果只写这一版面试官大概率会追问一句能不能不遍历完整棵树这就自然过渡到下面要讲的提前终止法了。4. 解法二中序遍历计数器提前终止4.1 用栈模拟递归的迭代写法提前终止的难点在于如果用递归写你很难在找到答案后立刻“跳出”整个递归过程。虽然可以用一个全局变量或者返回值来做标记但代码写起来总是变扭。所以更优雅的方式是改成迭代式的中序遍历用一个显式的栈来模拟递归的调用过程这样遍历到第 k 个节点时直接 return干净利落。class Solution { public int kthSmallest(TreeNode root, int k) { DequeTreeNode 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 个节点就停下最坏情况下 kn 才遍历完整棵树所以是 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) { DequeTreeNode 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 MapTreeNode, 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逻辑上更不容易搞错边界。如果你写成先比较后加一就变成“第 k1 小”了。6.3 空指针和退化树的处理测试用例不会给你空树但你别自己把代码写崩。在迭代版本里如果一棵树退化成了链状结构比如每个节点只有左孩子没有右孩子栈的深度会达到 n空间复杂度退化为 O(n)。虽然 LeetCode 的数据不会卡这个但面试时最好主动提一句这个问题说明你有考虑最坏情况。还有一个细节sizeMap.getOrDefault(node.left, 0)这行代码非常关键。如果左子树是 nullsizeMap里没有它的键直接 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 树的区间查询都会有那种“原来都是同一套路”的豁然感。这就是刷基础题最值得的地方。