LeetCode 230. 二叉搜索树中第 K 小的元素
📌 题目描述
题目级别：中等
给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第k小的元素（k从 1 开始计数）。
- 示例 1:
输入：root = [3,1,4,null,2], k = 1
输出：1
💡 破题思路：BST 的天生属性
二叉搜索树（BST）有一个最核心的性质：对 BST 进行“中序遍历”（左 -> 根 -> 右），得到的结果必定是一个严格递增的有序数组。
因此，找第k小的元素，其实就是做一次中序遍历，然后数到第k个停下来即可。
迭代法（栈）的优势：
如果使用递归进行中序遍历，很难在找到第k个元素后干净利落地立刻停止整棵树的遍历（除非抛异常或使用复杂的全局标记）。
而使用**栈（Stack）**手动模拟递归，我们可以精准控制流程：
- 不断往左子树深入，沿途节点全部压栈（最先出栈的一定是最左下的最小节点）。
- 弹出栈顶节点，这就是当前遍历到的最小元素，
k减 1。 - 如果
k == 0，说明找到了，立刻break返回结果，提前下班！ - 否则，将指针指向该节点的右子树，继续寻找。
💻 C++ 代码实现 (栈迭代法)
classSolution{public:intkthSmallest(TreeNode*root,intk){stack<TreeNode*>st;// 当指针不为空，或者栈里还有元素时，继续遍历while(root!=nullptr||!st.empty()){// 1. 一路向左，把所有左孩子压入栈中while(root!=nullptr){st.push(root);root=root->left;}// 2. 弹出栈顶元素（当前树中最小的待处理元素）root=st.top();st.pop();// 3. 计数器减 1，如果归零，说明就是我们要找的第 K 小元素k--;if(k==0)break;// 4. 转向右子树root=root->right;}returnroot->val;}};
