173. 二叉搜索树迭代器
2021年3月28日
让你实现二叉搜索树的迭代器,实现中序遍历
\(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();
}
};
标签:BSTIterator,迭代,int,dfs,st,ans,二叉,173
From: https://www.cnblogs.com/CrossAutomaton/p/17867546.html