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)``,其中 只保存节点指针,不复制也不拥有树节点。