LeetCode刷題筆記 230. 二叉搜尋樹中第K小的元素
- 遞歸
- 疊代
二叉搜尋樹中第K小的元素
遞歸
class Solution {
private:
int n=0,res;
public:
void dfs(TreeNode* root,int k){
if(!root) return;
dfs(root->left,k);
n++;
if(n==k) res=root->val;
dfs(root->right,k);
}
int kthSmallest(TreeNode* root, int k) {
dfs(root,k);
return res;
}
};
疊代
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
int res,n=0;
TreeNode *cur=root;
while(!s.empty()||cur){
while(cur){
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
n++;
if(n==k) return cur->val;
cur=cur->right;
}
return 0;
}
};