一、题目描述给定一个二叉搜索树的根节点root以及一个整数k请你返回其中第k小的元素。注意k从 1 开始计数。二叉搜索树BST的中序遍历结果是一个严格递增序列。示例输入root [3,1,4,null,2] k 1对应二叉树3 / \ 1 4 \ 2中序遍历1 2 3 4第 1 小1输出1另一个例子输入root [5,3,6,2,4,null,null,1] k 3结构5 / \ 3 6 / \ 2 4 / 1中序遍历1 2 3 4 5 6第 3 小3输出3二、为什么这道题值得学习这道题是二叉搜索树中的经典题也是面试高频题。它主要考察BST 的中序遍历性质递归遍历控制如何提前结束搜索1. 二叉搜索树的重要性质BST 满足左子树节点 根节点 右子树节点例如5 / \ 3 8 / \ 1 4中序遍历1 3 4 5 8可以发现BST 的中序遍历结果一定是递增序列所以第 k 小元素等价于中序遍历中的第 k 个节点。三、核心思想中序遍历寻找第 K 个节点二叉搜索树左 ↓ 根 ↓ 右刚好按照从小到大访问节点。例如4 / \ 2 6 / \ 1 3中序1 2 3 4 6如果k 3那么答案3所以只需要遍历 BST每访问一个节点计数 1当计数等于 k 时记录答案四、递归三部曲1. 确定递归函数定义void inorder(TreeNode root)作用完成 BST 的中序遍历。同时维护count表示当前访问了多少个节点。维护result表示第 k 小元素。2. 确定递归终止条件如果节点为空说明没有节点可以访问。直接返回if(root null){ return; }3. 确定单层递归逻辑第一步访问左子树inorder(root.left);因为左边更小。第二步访问当前节点计数count;判断if(count k)找到答案。第三步访问右子树inorder(root.right);五、解法一递归中序遍历面试推荐 ✅class Solution { int count 0; int result 0; public int kthSmallest(TreeNode root, int k) { inorder(root, k); return result; } private void inorder(TreeNode root, int k){ if(root null){ return; } // 遍历左子树 inorder(root.left,k); // 访问当前节点 count; if(count k){ result root.val; return; } // 遍历右子树 inorder(root.right,k); } }六、过程图解例如5 / \ 3 6 / \ 2 4 / 1要求k 3中序遍历过程访问1count1继续2count2继续3count3满足count k所以答案3七、复杂度分析时间复杂度普通递归O(N)原因最坏情况下需要遍历所有节点。但是如果找到答案后提前停止平均O(Hk)其中H树高度k第 k 小位置空间复杂度递归调用栈O(H)平衡树O(logN)最坏链状树O(N)八、常见错误与避坑指南❌ 错误一直接排序数组很多人想到遍历所有节点↓放入数组↓排序↓返回第 k 个虽然可以但是没有利用 BST 特性。时间O(NlogN)而中序遍历O(N)❌ 错误二前序遍历寻找错误根 → 左 → 右例如5 / 3前序5 3不是递增。无法判断第 k 小。❌ 错误三忘记 k 从 1 开始题目k 从 1 开始所以第一个访问节点count 1不是count 0九、另一种方法迭代中序遍历使用栈模拟递归核心不断向左走。遇到节点弹出访问。然后进入右子树。代码class Solution { public int kthSmallest(TreeNode root, int k) { StackTreeNode stack new Stack(); while(true){ while(root ! null){ stack.push(root); root root.left; } root stack.pop(); k--; if(k 0){ return root.val; } root root.right; } } }十、面试高频追问1️⃣ 为什么 BST 第 k 小可以用中序遍历因为BST 的中序遍历结果一定是升序排列所以第 k 个节点就是第 k 小元素。2️⃣ 能不能优化可以。如果 BST 节点额外保存左子树节点数量那么可以利用类似二分查找的方法快速定位第 k 小。时间O(logN)3️⃣ 为什么不用层序遍历因为层序遍历按照从上到下访问。不符合 BST 的大小顺序。总结LeetCode 230 的核心不是遍历整棵树而是利用BST 中序遍历 升序序列通过递归左子树 ↓ 当前节点 ↓ 右子树