0173. Binary Search Tree Iterator
=================================
题目信息
--------
:题号: 0173. 二叉搜索树迭代器
:难度: Medium
:主题: 二叉搜索树、迭代器、惰性中序遍历、栈
:原题: `LeetCode 0173 `_
:重点: 把递归中序遍历的续点压缩成左边界栈,使 next 均摊常数时间且只占树高空间
题目重述
--------
为一棵二叉搜索树实现 ``BSTIterator``:
* 构造函数接收根节点;
* ``next()`` 返回中序序列中的下一个值,也就是尚未返回的最小值;
* ``hasNext()`` 判断是否还有下一个值。
调用方保证只在 ``hasNext()`` 为真时调用 ``next()``。目标是让 ``next()`` 的均摊时间为
``O(1)``,迭代器额外占用 ``O(h)`` 空间,其中 ``h`` 是树高。
自建示例
--------
.. code-block:: text
7
/ \
3 15
/ \
9 20
调用顺序:next, next, hasNext, next, next, next, hasNext
返回结果:3, 7, true, 9, 15, 20, false
中序顺序是 ``3,7,9,15,20``,也就是 BST 的递增顺序。
.. code-block:: text
输入:root = []
构造后:hasNext() == false
空树没有任何节点,构造阶段不会向栈中写入状态。
C++ 实现
--------
.. code-block:: cpp
#include
class BSTIterator {
private:
std::vector pending_;
void pushLeftBoundary(TreeNode* node) {
while (node != nullptr) {
pending_.push_back(node);
node = node->left;
}
}
public:
BSTIterator(TreeNode* root) {
pushLeftBoundary(root);
}
int next() {
TreeNode* node = pending_.back();
pending_.pop_back();
pushLeftBoundary(node->right);
return node->val;
}
bool hasNext() {
return !pending_.empty();
}
};
题解
----
完整中序序列是正确但过早的工作
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
BST 的中序遍历按照“左子树、根、右子树”访问节点,输出天然递增。最直观的设计是在构造
函数中完成整棵树的中序遍历,把全部 ``n`` 个值存入数组;之后 ``next`` 只移动数组下标。
这个方案正确,单次查询也快,但即使调用方只取前几个值,构造阶段仍访问并保存全部节点,
空间为 ``O(n)``,没有达到 ``O(h)`` 目标。迭代器真正需要保存的不是完整未来输出,而是
“递归遍历暂停在何处、接下来该恢复哪些节点”。
递归调用栈保存的续点
~~~~~~~~~~~~~~~~~~~~
普通中序递归的控制流是:
.. code-block:: text
inorder(node.left)
visit(node)
inorder(node.right)
当递归不断进入左孩子时,每个祖先都在等待“左子树完成后访问我”。这些尚未访问的祖先
就是必要续点。``pushLeftBoundary(node)`` 沿当前子树的最左路径逐个压栈,模拟递归连续
进入左子树,直到遇到空指针才暂停。
最后压入的节点没有更深的左孩子,所以它是该子树中第一个应访问的节点;在 BST 中,它
也是该子树最小值。栈更低位置则保存未来需要恢复的祖先。
核心不变量
~~~~~~~~~~
每个公共操作结束后,``pending_`` 维护以下状态:
* 栈顶节点的左子树已经处理完,它是整个未返回集合中的下一个节点;
* 栈中更低的节点是中序递归尚未执行 ``visit`` 的祖先续点;
* 还没有压栈的未返回节点,只位于某个待访问节点尚未展开的右子树中。
构造时压入根的最左路径,正好建立这个不变量。只保存一条由递归续点组成的边界,而不是
所有未访问节点,是空间从 ``O(n)`` 降到 ``O(h)`` 的关键。
``next`` 如何恢复遍历
~~~~~~~~~~~~~~~~~~~~~
设栈顶为 ``node``。它的左侧工作已经完成,所以弹出并返回它等价于执行中序遍历的
``visit(node)``。接下来不能直接回到祖先,因为中序顺序要求先处理 ``node->right``。
右子树若存在,其中最先返回的不是右孩子本身,而是右子树的最左后代。因此弹出节点后,
代码对其右孩子调用 ``pushLeftBoundary``,把这棵右子树从根到最左节点的路径压入栈,
重新建立同一不变量。若右孩子为空,什么也不压入,原栈中的祖先自然成为下一续点。
这个顺序不能交换:若先返回右孩子而不压入它的左链,会跳过比右孩子更小的节点;若弹出
栈顶前先处理右子树,则会违背“根先于右子树”的中序顺序。
具体状态走读
~~~~~~~~~~~~
以上面示例树为例,栈按“底部 -> 顶部”书写:
.. code-block:: text
操作 返回 操作后的 pending_ 状态含义
构造 - [7,3] 3 是最左节点
next() 3 [7] 3 无右子树,恢复祖先 7
next() 7 [15,9] 进入 7 的右子树并压入左链
next() 9 [15] 9 无右子树,恢复祖先 15
next() 15 [20] 进入 15 的右子树
next() 20 [] 全部节点已经返回
第二次 ``next`` 中,弹出 7 后不能只压入 15;还必须继续压入 15 的左孩子 9,确保栈顶仍
是未返回最小值。对纯左链,所有节点在构造时入栈并从最小到最大弹出;对纯右链,每次只
在弹出后压入下一个右孩子。
``hasNext`` 为何只检查栈
~~~~~~~~~~~~~~~~~~~~~~~~
只要栈非空,核心不变量保证栈顶就是一个尚未返回的合法节点。若栈为空,就既没有等待访问
的根节点,也没有挂在这些续点之后的未展开右子树,遍历已经完成。因此
``hasNext()`` 与 ``!pending_.empty()`` 完全等价,不需要额外计数或树节点总数。
正确性与复杂度
~~~~~~~~~~~~~~
初始化建立中序续点不变量;每次 ``next`` 返回栈顶,并通过展开右子树的最左路径恢复
不变量。因此输出与完整中序遍历一致。BST 性质保证该序列递增,树的单父节点结构又保证
每个节点只会作为根路径或某个右子树左边界的一部分入栈一次,随后出栈一次,不重不漏。
构造最多沿一条左链工作,时间和空间为 ``O(h)``;``hasNext`` 为 ``O(1)``。单次
``next`` 最坏可能压入一条长度 ``O(h)`` 的左链,但整个迭代期间每个节点只入栈、出栈
各一次,总时间 ``O(n)``,所以 ``next`` 均摊 ``O(1)``。栈深最多为 ``O(h)``,其中
只保存节点指针,不复制也不拥有树节点。