本题用中序遍历加上一个额外的储存栈来输出第k个则空间复杂度会增加，拿不了满分
![]()
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int res=0; int cnt=0; bool flag=false; int minval=-1; int kthSmallest(TreeNode* root, int k) { dfs(root,k); return res; } void dfs(TreeNode* t,int k) { if(t==nullptr||flag==true) { return ; } dfs(t->left, k); if(t->val>minval) { cnt++; minval=t->val; if(cnt==k) { flag=true; res=t->val; } } dfs(t->right,k); } };
