2021年3月28日
173. 二叉搜索树迭代器
让你实现二叉搜索树的迭代器，实现中序遍历
\(next()\)返回元素，并使迭代器下移一个
\(hasnext()\)返回是否存在
两种方法，非递归和递归
- 递归写法
没啥难度，就普通的遍历，将数值存入queue就是了
class BSTIterator {
private:
queue<int> q;
public:
BSTIterator(TreeNode *root) {
dfs(root);
}
void dfs(TreeNode *p) {
if (p) {
dfs(p->left);
q.push(p->val);
dfs(p->right);
}
}
int next() {
int ans = q.front();
q.pop();
return ans;
}
bool hasNext() {
return !q.empty();
}
};
- 非递归写法
方法差不多，把dfs拆了就是了。
class BSTIterator {
private:
queue<int> q;
public:
BSTIterator(TreeNode *root) {
stack<TreeNode *> st;
TreeNode *p = root;
while (p || !st.empty()) {
//优先左走
if (p) {
st.push(p);
p = p->left;
} else {
//走不动了，看一下右边
p = st.top();
st.pop();
q.push(p->val);
p = p->right;
}
}
}
int next() {
int ans = q.front();
q.pop();
return ans;
}
bool hasNext() {
return !q.empty();
}
};