二叉搜索树中第k小的元素
本题用中序遍历加上一个额外的储存栈来输出第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 res0; int cnt0; bool flagfalse; int minval-1; int kthSmallest(TreeNode* root, int k) { dfs(root,k); return res; } void dfs(TreeNode* t,int k) { if(tnullptr||flagtrue) { return ; } dfs(t-left, k); if(t-valminval) { cnt; minvalt-val; if(cntk) { flagtrue; rest-val; } } dfs(t-right,k); } };
)
