山西省网站建设_网站建设公司_域名注册_seo优化

输入：二叉搜索树根节点root，整数k（从 1 开始计数）。

要求：返回 BST 中第k小的元素。

输出：一个整数（第k小的节点值）。

思路：

BST + 中序遍历的经典应用：
BST 的中序遍历结果是严格递增序列，所以“第 k 小” = “中序遍历第 k 个访问到的节点”。

1. 用k作为计数器（引用传递）
   中序遍历每访问一个节点就--k，当k == 0时当前节点值就是答案。

2. 提前结束遍历（剪枝）
   递归函数返回bool：

   • true表示已经找到答案，沿递归栈一路返回，不再继续遍历右子树/后续节点。
     这样避免无意义的遍历，尤其当k很小的时候很省事。

复杂度：

• 时间复杂度：O(H + k)（最坏 O(N)）
  走到最左边需要 O(H)，然后访问到第 k 个需要 O(k)。极端情况下退化到 O(N)。
• 空间复杂度：O(H)
  递归栈深度等于树高。

classSolution{public:intkthSmallest(TreeNode*root,intk){ans=-1;inorder(root,k);returnans;}private:intans;// 返回 true 表示已经找到答案，后续直接提前结束boolinorder(TreeNode*node,int&k){if(!node)returnfalse;if(inorder(node->left,k))returntrue;if(--k==0){ans=node->val;returntrue;}returninorder(node->right,k);}};