力扣 hot100 Day45

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

//抄的
class Solution {
public:   void helper(TreeNode* root,int k,int& count,int& result){   if(!root) return;helper(root->left,k,count,result);count++;if(count==k){result = root->val;return;}helper(root->right,k,count,result);}int kthSmallest(TreeNode* root, int k) {int count=0;int result;helper(root,k,count,result);return result;}
};

二叉搜索树的中序遍历结果必定是一个升序序列​

在中序遍历的逻辑基础上，维护一个count引用进行计数，与k进行对比，就能够遍历到第k小的元素。

可以考虑用显式栈替换递归栈进行中序遍历，可以避免递归栈溢出，如下

//抄的
class Solution {
public:   int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> st;int count = 0;while (root || !st.empty()) {while (root) {  // 遍历左子树st.push(root);root = root->left;}root = st.top();st.pop();count++;if (count == k) return root->val;root = root->right;  // 遍历右子树}return -1;  // 如果 k 超出范围}
};