0173. Binary Search Tree Iterator

题目信息

题号:
  1. 二叉搜索树迭代器

难度:

Medium

主题:

二叉搜索树、迭代器、惰性中序遍历、栈

原题:

LeetCode 0173

重点:

把递归中序遍历的续点压缩成左边界栈,使 next 均摊常数时间且只占树高空间

题目重述

为一棵二叉搜索树实现 BSTIterator:

  • 构造函数接收根节点;

  • next() 返回中序序列中的下一个值,也就是尚未返回的最小值;

  • hasNext() 判断是否还有下一个值。

调用方保证只在 hasNext() 为真时调用 next()。目标是让 next() 的均摊时间为 O(1),迭代器额外占用 O(h) 空间,其中 h 是树高。

自建示例

      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 的递增顺序。

输入:root = []
构造后:hasNext() == false

空树没有任何节点,构造阶段不会向栈中写入状态。

C++ 实现

#include <vector>

class BSTIterator {
private:
    std::vector<TreeNode*> 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) 目标。迭代器真正需要保存的不是完整未来输出,而是 “递归遍历暂停在何处、接下来该恢复哪些节点”。

递归调用栈保存的续点

普通中序递归的控制流是:

inorder(node.left)
visit(node)
inorder(node.right)

当递归不断进入左孩子时,每个祖先都在等待“左子树完成后访问我”。这些尚未访问的祖先 就是必要续点。pushLeftBoundary(node) 沿当前子树的最左路径逐个压栈,模拟递归连续 进入左子树,直到遇到空指针才暂停。

最后压入的节点没有更深的左孩子,所以它是该子树中第一个应访问的节点;在 BST 中,它 也是该子树最小值。栈更低位置则保存未来需要恢复的祖先。

核心不变量

每个公共操作结束后,pending_ 维护以下状态:

  • 栈顶节点的左子树已经处理完,它是整个未返回集合中的下一个节点;

  • 栈中更低的节点是中序递归尚未执行 visit 的祖先续点;

  • 还没有压栈的未返回节点,只位于某个待访问节点尚未展开的右子树中。

构造时压入根的最左路径,正好建立这个不变量。只保存一条由递归续点组成的边界,而不是 所有未访问节点,是空间从 O(n) 降到 O(h) 的关键。

next 如何恢复遍历

设栈顶为 node。它的左侧工作已经完成,所以弹出并返回它等价于执行中序遍历的 visit(node)。接下来不能直接回到祖先,因为中序顺序要求先处理 node->right。

右子树若存在,其中最先返回的不是右孩子本身,而是右子树的最左后代。因此弹出节点后, 代码对其右孩子调用 pushLeftBoundary,把这棵右子树从根到最左节点的路径压入栈, 重新建立同一不变量。若右孩子为空,什么也不压入,原栈中的祖先自然成为下一续点。

这个顺序不能交换:若先返回右孩子而不压入它的左链,会跳过比右孩子更小的节点;若弹出 栈顶前先处理右子树,则会违背“根先于右子树”的中序顺序。

具体状态走读

以上面示例树为例,栈按“底部 -> 顶部”书写:

操作          返回  操作后的 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),其中 只保存节点指针,不复制也不拥有树节点。