ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode 173 二叉搜索树迭代器 [打印本页]

---

作者: 耶耶耶耶耶    时间: 昨天 10:27
标题: LeetCode 173 二叉搜索树迭代器
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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4