LeetCode 173 二叉搜索树迭代器

耶耶耶耶耶  金牌会员 | 昨天 10:27 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 863|帖子 863|积分 2589

LeetCode 173: 二叉搜索树迭代器

题目描述：
实现一个二叉搜索树迭代器 (BSTIterator)，基于二叉搜索树（BST）的中序遍历，按升序遍历其节点值。具有以下利用：


  • BSTIterator(TreeNode root)：初始化对象并将指针设置为二叉树中的最小元素。
  • int next()：返回 BST 的下一个最小元素。
  • boolean hasNext()：如果指针指向的元素不是 BST 的最后一个元素，返回 true，否则返回 false。
题解思绪

中序遍历是 左 -> 根 -> 右 顺序。二叉搜索树特性是左子树的值小于根节点，右子树的值大于根节点。因此中序遍历二叉搜索树会得到一个递增的序列。
本题需要办理的题目：


  • 高效地返回 BST 的下一个最小值。
  • 较低的空间复杂度（尽量不一次性将所有节点存储起来）。
解法 1：直接存储中序遍历序列

思绪：


  • 在构造函数中对 BST 执行一次完全的中序遍历，将所有节点值存储到一个列表 inOrderList 中。
  • 使用一个指针 index 来标记当前 next() 返回的元素索引。
  • hasNext() 判定 index 是否超过 inOrderList 的最大索引。
模板代码：

  1. class BSTIterator {
  2.     private List<Integer> inOrderList;
  3.     private int index;
  5.     public BSTIterator(TreeNode root) {
  6.         inOrderList = new ArrayList<>();
  7.         index = 0;
  8.         inOrderTraversal(root); // 构造中序遍历序列
  9.     }
  11.     /** 中序遍历，存储到列表中 */
  12.     private void inOrderTraversal(TreeNode root) {
  13.         if (root == null) return;
  14.         inOrderTraversal(root.left);
  15.         inOrderList.add(root.val);
  16.         inOrderTraversal(root.right);
  17.     }
  19.     /** 返回 BST 中的下一个最小值 */
  20.     public int next() {
  21.         return inOrderList.get(index++);
  22.     }
  24.     /** 判断是否还有下一个值 */
  25.     public boolean hasNext() {
  26.         return index < inOrderList.size();
  27.     }
  28. }
复制代码
时间和空间复杂度：



  • 时间复杂度：

    • 构造函数：O(N)，需要对 BST 完整遍历一遍。
    • next() 和 hasNext()：O(1)。

  • 空间复杂度：

    • 存储 inOrderList：O(N)。

  • 长处：

    • 逻辑简单，实现容易。

  • 缺点：

    • 空间复杂度较高（需存储整个树所有节点值）。

解法 2：迭代 + 栈

思绪：


  • 基于中序遍历的特性，使用显式栈来模仿递归的调用栈。

    • 中序遍历需要先处理左子树，直到找到最左端。
    • 然后处理根节点，最后处理右子树。

  • 在初始化时，将从根节点出发，沿左子树路径上的所有节点压入栈。
  • next() 时，从栈中弹出栈顶节点：

    • 如果该节点有右子树，则对右子树执行相同利用（即将右子树路径上的所有左节点压入栈）。

  • hasNext() 简单检查栈是否为空。
模板代码：

  1. class BSTIterator {
  2.     private Stack<TreeNode> stack;
  4.     public BSTIterator(TreeNode root) {
  5.         stack = new Stack<>();
  6.         pushLeft(root); // 初始化时沿左子树一路压栈
  7.     }
  9.     /** 将 root 节点的所有左子树节点压入栈 */
  10.     private void pushLeft(TreeNode root) {
  11.         while (root != null) {
  12.             stack.push(root);
  13.             root = root.left;
  14.         }
  15.     }
  17.     /** 返回 BST 中的下一个最小值 */
  18.     public int next() {
  19.         TreeNode node = stack.pop();
  20.         // 如果节点有右子树，对右子树重复压栈操作
  21.         if (node.right != null) {
  22.             pushLeft(node.right);
  23.         }
  24.         return node.val;
  25.     }
  27.     /** 判断是否还有下一个值 */
  28.     public boolean hasNext() {
  29.         return !stack.isEmpty();
  30.     }
  31. }
复制代码
时间和空间复杂度：



  • 时间复杂度：

    • next()：均派 O(1)。每个节点被压栈和弹栈各一次，总共为 O(N)。
    • hasNext()：O(1)。

  • 空间复杂度：

    • 最坏环境下 O(H)，其中 H 是 BST 的高度（栈中最多存储完整的树高路径）。

  • 长处：

    • 空间服从更高，尤其是对于稀疏树或深度较大的 BST。

  • 缺点：

    • 实现略复杂。

解法 3：递归生成器

使用 Java 的递归生成器（基于队列模仿生成器），一次处理一个值。

思绪：


  • 使用一个队列 queue 存储中序遍历的节点值。
  • 初始化时通过递归中序遍历，将节点值入队。
  • 在 next() 时，从队头取值；hasNext() 检查队列是否为空。
模板代码：

  1. class BSTIterator {
  2.     private Queue<Integer> queue; // 使用队列存储中序遍历结果
  4.     public BSTIterator(TreeNode root) {
  5.         queue = new LinkedList<>();
  6.         inOrderTraversal(root);
  7.     }
  9.     /** 中序遍历，将节点值入队 */
  10.     private void inOrderTraversal(TreeNode root) {
  11.         if (root == null) return;
  12.         inOrderTraversal(root.left);
  13.         queue.offer(root.val);
  14.         inOrderTraversal(root.right);
  15.     }
  17.     /** 返回 BST 中的下一个最小值 */
  18.     public int next() {
  19.         return queue.poll();
  20.     }
  22.     /** 判断是否还有下一个值 */
  23.     public boolean hasNext() {
  24.         return !queue.isEmpty();
  25.     }
  26. }
复制代码
时间和空间复杂度：



  • 时间复杂度：

    • 构造函数：O(N)，一次构建中序遍历结果。
    • next() 和 hasNext()：O(1)。

  • 空间复杂度：

    • 队列存储中序遍历结果，空间复杂度为 O(N)。

  • 长处：

    • 简单明白，易于明白。

  • 缺点：

    • 空间服从不佳，与解法 1 类似。

快速 AC 的发起



  • 对于实际口试场景，发起优先选择 解法 2（迭代 + 栈）：

    • 它时间和空间服从较高，是真正的「惰性遍历」。
    • 运用了栈来模仿递归过程，是二叉树迭代题目的普适模板。

  • 初始实现逻辑简单的环境下，可以实现 解法 1（存储序列）。
  • 生成器法（解法 3）可以用于创建类似流式数据的接口实现。
经典变体题目

1. Binary Search Tree Preorder Iterator



  • 题目： 按照「先序遍历」（根 -> 左 -> 右）的顺序实现类似的 Iterator。
  • 解法：

    • 使用栈来模仿先序遍历。
    • 每次 next() 弹出栈顶节点，同时将 右子树 和 左子树（留意顺序）依次入栈。

  1. class PreorderIterator {
  2.     private Stack<TreeNode> stack;
  4.     public PreorderIterator(TreeNode root) {
  5.         stack = new Stack<>();
  6.         if (root != null) stack.push(root);
  7.     }
  9.     public boolean hasNext() {
  10.         return !stack.isEmpty();
  11.     }
  13.     public int next() {
  14.         TreeNode node = stack.pop();
  15.         if (node.right != null) stack.push(node.right); // 右子树先入栈
  16.         if (node.left != null) stack.push(node.left);   // 左子树后入栈
  17.         return node.val;
  18.     }
  19. }
复制代码
2. Postorder Iterator



  • 题目： 按照「后序遍历」（左 -> 右 -> 根）实现迭代器。
  • 解法：

    • 利用双栈实现：第一栈模仿 root-right-left 的顺序，第二栈翻转为真正的后序遍历结果。
    • 使用一个布尔变量标记访问状态，写法略复杂。

  1. class PostorderIterator {
  2.     private Stack<TreeNode> stack1;
  3.     private Stack<TreeNode> stack2;
  5.     public PostorderIterator(TreeNode root) {
  6.         stack1 = new Stack<>();
  7.         stack2 = new Stack<>();
  8.         if (root != null) stack1.push(root);
  10.         while (!stack1.isEmpty()) {
  11.             TreeNode node = stack1.pop();
  12.             stack2.push(node);
  13.             if (node.left != null) stack1.push(node.left);
  14.             if (node.right != null) stack1.push(node.right);
  15.         }
  16.     }
  18.     public boolean hasNext() {
  19.         return !stack2.isEmpty();
  20.     }
  22.     public int next() {
  23.         return stack2.pop().val;
  24.     }
  25. }
复制代码
3. 二叉树层序遍历迭代器



  • 题目： 按照「层序遍历」（逐层从上到下、从左到右）的顺序实现迭代器。
  • 解法：

    • 使用队列来模仿层序遍历。

  1. class LevelOrderIterator {
  2.     private Queue<TreeNode> queue;
  4.     public LevelOrderIterator(TreeNode root) {
  5.         queue = new LinkedList<>();
  6.         if (root != null) queue.offer(root);
  7.     }
  9.     public boolean hasNext() {
  10.         return !queue.isEmpty();
  11.     }
  13.     public int next() {
  14.         TreeNode node = queue.poll();
  15.         if (node.left != null) queue.offer(node.left);
  16.         if (node.right != null) queue.offer(node.right);
  17.         return node.val;
  18.     }
  19. }
复制代码
总结


  • 核心解法：

    • 解法 2（迭代 + 栈）是最核心的技巧，适用于惰性遍历场景，推荐用于实际使用和口试。

  • 经典变种：

    • 各类二叉树遍历模式（中序、先序、后序、层序）的迭代器实现都可以通过栈或队列模仿递归来实现。

  • 快速 AC 的关键：

    • 掌握递归和迭代的转换，机动选择数据布局（栈或队列）。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

正序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

耶耶耶耶耶

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

存储 挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表