给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
方法一、中序遍历、
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void inorder(TreeNode* root,vector<int>&res){if(root==NULL)return;inorder(root->left,res);res.push_back(root->val);inorder(root->right,res);}int kthSmallest(TreeNode* root, int k) {vector<int> res;//利用二叉搜索树的特性，中序遍历，将最后的结果存入res中inorder(root,res);return res[k-1];}
};
方法二、非递归的方式
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode *> st;//按照中序遍历的方式遍历while (!st.empty() || root) {//如果root不为零，先将root推入栈，在遍历左子树while (root) {st.push(root);root = root->left;}// now root is empty//使得root不为空root = st.top();//弹出st.pop();k--;if (k == 0) {return root->val;}//遍历右子树root = root->right;}return -1;}
};