给定一个二叉搜索树(BST)，找到树中第 K 小的节点。

解法一：中序遍历

对于二叉搜索树，中序遍历得到的序列是递增有序的。因此，我们可以通过中序遍历得到所有的节点值，然后返回第 K 小的节点值。

代码实现：

class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> vals;
inorder(root, vals);
return vals[k-1];
}

void inorder(TreeNode* root, vector<int>& vals) {
if (root == nullptr) {
return;
}
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
};

时间复杂度：O(N)，其中 N 为二叉搜索树节点的个数，最坏情况下需要遍历所有的节点。

解法二：迭代法

通过迭代中序遍历可以在遍历时统计已经遍历的节点个数，一旦遍历到第 K 个节点就返回该节点的值。

代码实现：

class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
TreeNode* p = root;
int count = 0;
while (p != nullptr || !s.empty()) {
while (p != nullptr) {
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
++count;
if (count == k) {
return p->val;
}
p = p->right;
}
return -1;
}
};

时间复杂度：O(N)，其中 N 为二叉搜索树节点的个数，最坏情况下需要遍历所有的节点。