青海省网站建设_网站建设公司_内容更新_seo优化

输入：BST 根节点root，构造BSTIterator。

要求：
实现一个按中序遍历输出 BST 的迭代器：

• next()：返回下一个最小值
• hasNext()：是否还有下一个元素

输出：按题意实现类方法（next/hasNext）。

思路：

思路 A：中序遍历“展开成线性表”

核心就是一句话：

BST 中序遍历 = 递增序列
先把整棵树中序遍历一遍，把结果按顺序塞进链表/数组，然后迭代器只是在这个线性结构上移动指针。

1. 构造时inorder(root)，按中序顺序把每个节点值 append 到单链表尾部。
2. cur指向链表头（第一个最小值）。
3. next()返回cur->val并前进。
4. hasNext()看cur != nullptr。

优点：

• 写起来直观，next/hasNext都是 O(1)。

缺点：

• 构造函数要遍历整棵树，时间 O(N)。
• 额外存了 N 个节点值，空间 O(N)。
• 题目进阶想要更省空间（典型答案是 O(H)）。

思路 B：用栈模拟中序遍历（更优解的核心思想）

迭代器本质是：每次只走到“下一个该访问的中序节点”，不提前把整棵树铺开。

维护一个栈stk：

• 构造时：把root的整条左链压栈（走到最左）。
• next()：
  1. 弹出栈顶x（当前最小）
  2. 如果x有右子树，把x->right的整条左链压栈
  3. 返回x->val
• hasNext()：看栈空不空

复杂度：

• 思路 A（暴力）

  • 构造：O(N)
  • next/hasNext：O(1)
  • 空间：O(N)

• 思路 B（栈模拟）

  • 构造：O(H)
  • next：均摊 O(1)（每个节点最多入栈出栈一次）
  • 空间：O(H)

//思路A 暴力classBSTIterator{public:BSTIterator(TreeNode*root){dummy=newListNode(0);tail=dummy;inorder(root);cur=dummy->next;}intnext(){intval=cur->val;cur=cur->next;returnval;}boolhasNext(){returncur!=nullptr;}private:structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};ListNode*dummy;ListNode*tail;ListNode*cur;voidinorder(TreeNode*node){if(node==nullptr)return;inorder(node->left);tail->next=newListNode(node->val);tail=tail->next;inorder(node->right);}};//思路B 栈模拟classBSTIterator{public:BSTIterator(TreeNode*root){pushLeftChain(root);}intnext(){TreeNode*node=st.top();st.pop();intret=node->val;// 下一批候选：node 的右子树的最左链if(node->right){pushLeftChain(node->right);}returnret;}boolhasNext(){return!st.empty();}private:stack<TreeNode*>st;voidpushLeftChain(TreeNode*node){while(node){st.push(node);node=node->left;}}};