企业官网建设流程全解析

刷过 LeetCode Hot 100 的朋友应该都能感受到，二叉搜索树（BST）这一块几乎是必考内容。230 这道题，题面看起来简单——给定一棵二叉搜索树，找出其中第 K 小的元素，难度标着 Medium，但里面藏着的门道其实不少。很多人第一次见到这题，第一反应是“把树遍历一遍存到数组里，排序，取第 K 个”，但这显然不是出题人想看到的答案。它考察的其实是两个核心能力：一是对 BST 性质的理解，二是对递归和迭代两种遍历方式的掌握程度。这篇文章我就带着大家把这道题从里到外拆一遍，包括三种递进式的解法、每种解法的复杂度分析、日常刷题时容易踩的坑，以及它的变形题目，希望能帮你彻底吃透这道经典题。

这篇文章适合刚入门二叉树、准备面试算法题、或者二刷三刷 Hot 100 查漏补缺的读者。不管是想快速拿到 AC，还是想理解解法背后的原理，都能从这里面找到你想要的东西。

1. 题目拆解：为什么“中序遍历”是这道题的关键

1.1 先搞清楚二叉搜索树的核心性质

我在刷题过程中发现，很多朋友对二叉搜索树的印象停留在“左小右大”这四个字上，但实际写代码的时候又容易把性质用错。这里帮大家把性质梳理清楚，因为 230 这道题能解出来，靠的就是这几条性质。

二叉搜索树的定义是：对于树中的任意一个节点，它的左子树中所有节点的值都小于这个节点的值，它的右子树中所有节点的值都大于这个节点的值，并且左子树和右子树本身也必须是二叉搜索树。注意这里说的是“左子树中所有节点”，不只是左孩子，右子树同理。换句话说，整棵树天然就是一个排好序的结构，只不过这种“排序”不是线性的，而是沿着树的结构展开的。

这是一个非常强的性质。如果一棵 BST 是平衡的，那么查找一个节点的时间复杂度是 O(log n)，这和二分查找是同一个量级。但更值得我们注意的是另一个推论：对一棵 BST 进行中序遍历（左子树 → 根节点 → 右子树），得到的结果一定是一个递增序列。这一点就是 230 题的核心突破口。

为了加深印象，大家可以拿一棵具体的树来走一遍。假设我们有这样一棵 BST：

5 / \ 3 6 / \ \ 2 4 7

中序遍历的顺序是：先遍历 2 的左子树（空），输出 2，回根 3，输出 3，再遍历 3 的右子树，输出 4，然后回根 5，输出 5，接着去右子树，输出 6，最后输出 7。最终结果是 [2, 3, 4, 5, 6, 7]。可以看到，确实是严格递增的。

这意味着“找第 K 小的元素”这个任务，可以等价地转换成“在中序遍历序列中找第 K 个出现的节点”。如果这道题换成“找第 K 大的元素”，那做法就是反过来，用右子树 → 根节点 → 左子树的遍历顺序（逆中序遍历），找到第 K 个节点就行。

1.2 暴力解法的得与失

在给出最优解之前，先说说很多新手会采用的方式：把整棵树前序遍历或者层序遍历一遍，把所有节点值收集到一个数组中，然后排序，最后直接取第 K-1 个元素。

这样做能 AC 吗？对于 230 这道题来说，鉴于限制条件比较温和，确实可以。但问题是，这样做完全没有利用 BST 本身的特点，等于是把一个二叉搜索树问题降维成了普通的数组排序问题。时间复杂度是 O(n log n)，空间复杂度是 O(n)，对于操作一棵只有几百个节点的树来说没什么问题，但放到大数据量或面试环境里，这种写法就暴露了两个问题：

1. 面试官大概率会追问一句：“你能用 O(n) 时间、O(1) 空间解决吗？”
2. 这种解法没有体现你对数据结构的理解，代码写出来等于是在告诉面试官，“我知道怎么遍历树，但不知道中序遍历的性质”。

所以我们后面讲的解法，核心思路都是“边遍历边计数，找到第 K 个就停”，而不是从头到尾遍历完整棵树。这既能降低实际运行时间，也体现了对 BST 结构的深度利用。

2. 解法一：递归中序遍历 + 计数器

2.1 最简单的实现思路与代码

递归中序遍历应该是大家最先接触的遍历方式，思路非常直观：遍历左子树，处理当前节点，遍历右子树。我们要做的只是在“处理当前节点”这一步加一个计数器，当计数器等于 K 时记录答案并返回。

class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.count = 0 self.result = 0 def inorder(node): if not node or self.result != 0: return inorder(node.left) if self.result != 0: return self.count += 1 if self.count == k: self.result = node.val return inorder(node.right) inorder(root) return self.result

这里有几个小细节值得注意。第一，我在递归函数开头和左子树遍历完成后都判断了self.result != 0，这是提前终止条件。如果不加这个判断，即使已经找到了第 K 个节点，递归还是会继续遍历剩下的节点，浪费不必要的时间。第二，计数器的位置必须在“左子树递归之后、右子树递归之前”，这正好对应中序遍历的顺序。

2.2 执行过程模拟与时间复杂度分析

拿前面那棵树来走一遍，假设 K = 3。递归进入 5，先走左子树：进入 3，再走左子树：进入 2，2 的左子树为空，处理 2，此时 count = 1；回到 3，处理 3，count = 2；进入 3 的右子树，处理 4，count = 3，第 K 个元素找到了，result = 4，后续的递归会一路通过提前终止条件退出。

时间复杂度方面，最坏情况下 K = n，会遍历完整棵树，所以是 O(n)。平均情况下，如果树的形状比较平衡，执行 K 次递归后就会终止，可以近似认为是 O(K + h)，h 为树高。空间复杂度上，每一次递归调用都会占用栈空间，递归深度取决于树的高度。一棵平衡二叉树的高度是 O(log n)，但如果是退化成链表的树（比如连续递增的节点组成的右斜树），递归深度就是 O(n)，这也是递归解法的一个隐藏风险。

所以递归版本适合在树比较平衡、或者不希望写额外辅助数据结构时使用。但它有一个先天不足：无法真正做到提前“干净利落”地退出。虽然可以通过全局变量标记来模拟，但代码可读性会受一点影响。因此我更推荐大家掌握下面要讲的迭代版本。

3. 解法二：迭代中序遍历，手动模拟递归栈

3.1 为什么推荐迭代版本

现在不少公司的面试现场都会问“能用迭代实现吗”，因为你写递归很容易，但递归背后发生的事情（函数调用栈）不一定清楚。迭代版本的本质是手动维护一个栈，来模拟递归过程中系统栈的行为。这样做有两个直接的好处：一是摆脱了系统性递归深度限制，哪怕这棵树退化成一个链表，也不会出现栈溢出的风险；二是代码可以做到“找到第 K 个节点立即返回”，不需要额外设置全局标记。

3.2 代码实现与关键步骤拆解

迭代中序遍历的标准写法是：从根节点出发，一路把左孩子压入栈，直到左孩子为空；然后弹出栈顶节点，处理它；再把当前指针移到右孩子，重复上述过程。在 230 这道题里，我们只需要在处理节点时计数即可。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { stack<TreeNode*> stk; TreeNode* cur = root; while (cur != nullptr || !stk.empty()) { // 一路向左，把所有左孩子压栈 while (cur != nullptr) { stk.push(cur); cur = cur->left; } // 弹出栈顶节点，这是当前中序顺序的下一个节点 cur = stk.top(); stk.pop(); k--; if (k == 0) { return cur->val; } // 转向右子树，开始新一轮的“一路向左” cur = cur->right; } return -1; // 理论上不会走到这里 } };

这段代码的核心在于cur = cur->right这一步。很多人初学迭代中序遍历时会漏掉这个赋值，导致死循环。原因是：如果你处理完一个节点后不改变cur指针，下一步循环会继续从栈里弹出一个节点，但这个节点其实是当前节点的父节点，顺序就乱了。只有把cur指向右孩子，才能保证下一次“一路向左”是从右子树开始的，这正是中序遍历的逻辑。

3.3 复杂度与面试表现

这个迭代版本的时间复杂度和递归版本一致，最坏 O(n)，但实际运行中一旦 k 减到 0 就直接返回了，不需要遍历完整棵树，所以平均表现更好。空间复杂度是 O(h)，h 为树的高度，因为栈中最多保存从根到叶子的一条路径上的节点。对于一棵平衡 BST，h = log n，空间开销非常小。

面试时如果写这个版本，面试官一般会认可。但我还想补充一个更“炫酷”的进阶方案，那就是 Morris 遍历，它可以把空间复杂度压到真正的 O(1)。

4. 解法三：Morris 中序遍历——从 O(h) 到 O(1) 的进阶方案

4.1 Morris 遍历的核心思想：线索二叉树

很多初学者听到 Morris 遍历会觉得它是偏题怪题，但实际上它背后有一个很古典的概念——线索二叉树。简单来说，Morris 遍历的发明者是想解决“不用栈和递归，怎么实现树的遍历”这个问题。

前面我们用栈是因为：当我们从当前节点去遍历它的左子树时，遍历完成后需要回到当前节点去处理它，然后再去右子树。如果我们不在栈里记住“当前节点是谁”，等左子树遍历完就找不到回来的路了。那 Morris 是怎么解决这个问题的呢？答案是利用叶子节点空闲的左右指针，临时把“要回来的路”记下来。

具体到中序遍历的流程是：

1. 从根节点开始，把当前节点记为 cur。
2. 如果 cur 没有左孩子，那说明左子树为空，cur 就是当前中序顺序中该处理的节点，处理它，然后 cur 转向右孩子。
3. 如果 cur 有左孩子，在左子树中找到“中序遍历的最后一个节点”，也就是左子树中最右边的节点，把它记为 predecessor。这个节点在中序遍历中会紧挨在 cur 前面被访问。
4. 如果 predecessor 的右孩子为空，说明我们还没有建立线索，于是把 predecessor 的右孩子指向 cur，这相当于给左子树“装了一条回家的路”，然后 cur 转向左孩子。
5. 如果 predecessor 的右孩子指向了 cur，说明左子树已经遍历完了，此时需要恢复树结构，把 predecessor 的右孩子置回空，然后处理 cur，并把 cur 转向右孩子。

这个方法最巧妙的地方在于，它既不使用额外的数据结构，也没有在遍历完成后还留下线索，而是在节点访问完后立刻恢复原状。因此整棵树的形状在遍历结束后保持原样，没有任何残留改动。

4.2 Morris 中序遍历求解第 K 小的完整代码

class Solution { public int kthSmallest(TreeNode root, int k) { TreeNode cur = root; int count = 0; while (cur != null) { if (cur.left == null) { // 没有左孩子，直接处理当前节点 count++; if (count == k) { return cur.val; } cur = cur.right; } else { // 找左子树中最右节点 TreeNode predecessor = cur.left; while (predecessor.right != null && predecessor.right != cur) { predecessor = predecessor.right; } if (predecessor.right == null) { // 建立线索，然后向左移动 predecessor.right = cur; cur = cur.left; } else { // 左子树已遍历完，恢复树结构，处理当前节点 predecessor.right = null; count++; if (count == k) { return cur.val; } cur = cur.right; } } } return -1; } }

这个写法里我保留了count变量，每处理一个节点就加一。需要注意的是，在“处理当前节点”这一步，我们实际上只会在两种情况下执行：一是 cur 没有左孩子，此时左子树为空，cur 是中序顺序中的下一个；二是 predecessor.right == cur，说明左子树全部遍历完成，cur 又应该是中序顺序中的下一个。这两种情况加在一起，恰好覆盖了中序遍历中“当一个节点的左子树为空或者已经被访问完，就轮到它自己”这个逻辑。

4.3 Morris 遍历的代价与适用场景

Morris 遍历的时间复杂度依然是 O(n)，但每个节点最多被访问两次（一次是建立线索时路过，一次是通过线索回来时），所以常数比普通递归和迭代稍微大一点。不过它的空间复杂度是 O(1)，只用了两个指针，这是递归和迭代都做不到的。

我在实际刷题和面试中，对 Morris 遍历持这样的态度：如果面试官明确要求“你能不能设计一个 O(1) 空间复杂度的解法”，那 Morris 遍历是你的加分项；如果是日常刷题，理解它的原理比背上代码更重要。因为实际工程中，几乎不会有人用 Morris 遍历来处理树，毕竟修改了节点的指针又要恢复，这在并发环境下并不是一个安全的做法。但在算法面试的场景里，你能流畅写出 Morris 遍历的代码，说明你对树结构的理解已经超过绝大多数候选人了。

如果你第一次接触 Morris 遍历觉得有点绕，不用着急。建议你拿一棵三个节点的树，比如[2, 1, 3]，然后手动走一遍代码中每个分支，把每一次 cur 的移动和指针的改动都写下来，走完整整一遍后，这个思路就刻在脑子里了。

5. 三种解法对比与实战建议

5.1 复杂度对照表

为了让大家对三种解法有一个直观的对比，我整理了一张表格，方便在复习时快速回忆。

从表格里可以看到，三种解法在最坏情况下的时间量级是一致的，差距主要在空间和代码的可读性上。如果你在本地刷题，用递归版本最省心；如果你在准备面试，建议优先练习迭代版本，因为写完之后面试官一般不会追问“还能不能再优化空间”，毕竟 Morris 属于进阶内容，懂得原理就够了。

5.2 实际刷题中的推荐练习节奏

我自己的刷题习惯是：每道题先花 10 到 15 分钟独立思考，写出暴力解或最直观的解法，然后停下来想一想有没有更好的方案。针对 230 这道题，我推荐的练习顺序是：

第一步，先用递归中序遍历解决，保证自己能流畅写出代码，并理解计数器放在哪个位置。

第二步，隔半天到一天后，尝试不参考任何资料，手写一遍迭代解法。

第三步，如果时间充裕，研究一下 Morris 中序遍历，并尝试改编成求解第 K 大元素。

这个节奏看起来慢，但对记忆的巩固效果比一天刷三遍要强得多。我见过很多人刷题时直接看题解，看完觉得自己懂了，但过几天再写还是卡壳，原因就在于“看懂了”和“自己能写出来”之间还差着一个刻意练习的距离。

6. 边界条件与高频坑点

6.1 容易忽视的边界条件

230 这道题虽然代码看着不长，但边界条件其实不少。我把能想到的边界都列出来，大家可以对照着自己的代码检查一遍：

• K = 1 时：应该返回整棵树最左边的节点值。如果树是空树（这种情况题目一般不会给，但练习时值得考虑），需要想好返回什么。
• K = 树中节点总数时：应该返回整棵树最右边的节点值，也就是最大值。
• 树退化成一个只有右孩子的链：比如[1, null, 2, null, 3, null, 4]，此时中序遍历的结果就是 1, 2, 3, 4。如果你用递归解法，递归深度等于节点数，在大数据量下存在栈溢出风险。
• 树退化成一个只有左孩子的链：比如[4, 3, null, 2, null, 1]，中序遍历结果是 1, 2, 3, 4。迭代解法在这种情况下会频繁压栈，但栈的最大深度依然等于树高，同样需要注意。
• 所有节点的值都相同：这种情况不一定违反 BST 的定义，取决于题目对“严格大于/小于”还是“大于等于/小于等于”的约定。LeetCode 默认是严格版本，所以相同的值不会同时出现在树的上下层中，但练习时值得想一想。

6.2 那些年我们一起踩过的坑

我在给朋友 review 代码时，发现最常见的 bug 其实是计数器位置放错。有人把计数放在了递归调用左子树之前，结果统计的顺序变成了“先根、再左、再右”，也就是前序顺序，返回的自然是第 K 个前序节点的值，而不是第 K 小。

第二个常见问题是，有人试图在递归函数里直接返回node.val，却发现返回值被上层递归覆盖了。这是因为递归返回的是一个基本类型数值，无法把“已经找到第 K 个节点”这个状态一直传递到最外层。要解决这个问题，要么用全局变量，要么定义一个包含状态的对象。这也是为什么迭代版本更直观——你可以直接return cur.val，不需要处理状态传递。

第三个容易踩坑的地方是，有人为了提前终止递归，在找到结果后直接 return 了当前节点的值，但上层递归没有处理这个 return，导致结果丢失。正确的做法是用一个全局变量记录结果，然后再通过条件判断阻止后续递归。

还有一个细节是：很多人在迭代解法中漏掉cur = cur->right这一步，导致处理完左子树后，程序一直在左子树和根节点之间反复横跳，形成了死循环。这种 bug 一旦出现，排查起来并不轻松，因为执行过程看起来像是一个正常的遍历，但实际上陷入了局部循环。

7. 进阶思考：这道题能带给我们什么

7.1 从“找第 K 小”到“验证二叉搜索树”

230 这道题充分展示了“中序遍历结果递增”这个性质。而顺着这个思路往前走，我们会遇到一个非常经典的姊妹题：验证一棵二叉树是不是有效的二叉搜索树（LeetCode 98）。那道题本质上就是把“中序遍历是否严格递增”作为判断依据。

所以做 230 的时候，最好把中序遍历的代码模板牢牢记住。这个模板能一口气解决下面这些问题：

• 找第 K 小的元素（230）
• 找第 K 大的元素（改成先右后左的遍历顺序）
• 验证二叉搜索树（中序遍历后检查是否递增）
• 恢复一棵被错误交换了两个节点的二叉搜索树（99）
• 将二叉搜索树转为累加树（538）

如果你能一眼看出这些题目背后的共同点，说明你的抽象能力已经上了一个台阶。刷题要的不是一题一题地背，而是要能从一道题里发现一类题的通法。

7.2 如果 BST 会频繁修改（支持插入删除），还能这么写吗

这是我在面试中真实遇到过的一个追问。如果这棵二叉搜索树只会被查询一次，那我们中序遍历找到第 K 小，是最高效的方案。但如果这个系统需要高频执行查询和插入删除操作，每次都中序遍历显然不行。

此时更合适的数据结构是在树的每个节点上维护一个“子树节点数量”字段，然后利用 BST 的二分性质进行查找。具体思路是：从根节点开始，假设根的左子树有 L 个节点。如果 K 小于等于 L，说明第 K 小的元素在左子树中，递归进入左子树查找；如果 K 等于 L + 1，说明当前根节点就是第 K 小的元素；如果 K 大于 L + 1，说明在右子树中，并且要找的是右子树中第 K - L - 1 小的元素。

这种方法在平衡 BST 中的查询复杂度是 O(log n)，而且每次插入或删除时只需要更新路径上的节点数量字段，也是 O(log n)。这个思想还会出现在“有序统计树”（order statistic tree）中，是平衡树的高级应用之一。如果 230 让你觉得太简单，不妨试试能不能给树的节点结构加上一个size字段，然后实现插入、删除和查询第 K 小三个操作。

7.3 从一道题到一类题：掌握树遍历的心智模型

说回 230 本身。我觉得它最大的价值是帮助我们建立了一个关于树遍历的心智模型：递归遍历其实就是在“访问节点”这个动作上做文章。同样的模板，你在访问节点的位置输出就是打印，计数就是找第 K 小，比较前后值就是验证 BST。把模板吃透，剩下的事情就只是“在合适的时机做合适的事”。

我个人在实际刷题过程中，最深刻的体会是：真正难的从来不是把代码写出来，而是把“为什么这样写”想明白。比如为什么要先递归左子树？为什么处理完左子树后要回到当前节点？为什么迭代解法要找“最右节点”来建立线索？这些问题想通了，代码自然就记住了。

如果你读完这篇文章，能不看任何参考代码，自己画出三种解法的执行流程图，再写出代码，那这道题对你来说就算真正拿下了。如果还想加练，可以去把 LeetCode 98、99、538 这三道题拉出来一起刷一遍，四道题放在一起刷，印象会非常深刻。

最后再分享一个我自己的小习惯：每当我在 LeetCode 上遇到一道不错的二叉树题目，我都会在本地 IDE 里配一个用于打印树结构的工具函数，这样调试的时候能一眼看出每一轮遍历后树的状态变化。别小看这个动作，调试 Morris 遍历的时候，它就是救命的稻草。