北京排名seo优化渠道_生活中的科技产品有哪些_seo顾问服务品达优化_seopeix

LeetCode 173: 二叉搜索树迭代器

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

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

题解思路

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

本题需要解决的问题：

高效地返回 BST 的下一个最小值。
较低的空间复杂度（尽量不一次性将所有节点存储起来）。

解法 1：直接存储中序遍历序列

思路：

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

模板代码：

class BSTIterator {private List<Integer> inOrderList;private int index;public BSTIterator(TreeNode root) {inOrderList = new ArrayList<>();index = 0;inOrderTraversal(root); // 构造中序遍历序列}/** 中序遍历，存储到列表中 */private void inOrderTraversal(TreeNode root) {if (root == null) return;inOrderTraversal(root.left);inOrderList.add(root.val);inOrderTraversal(root.right);}/** 返回 BST 中的下一个最小值 */public int next() {return inOrderList.get(index++);}/** 判断是否还有下一个值 */public boolean hasNext() {return index < inOrderList.size();}
}

时间和空间复杂度：

时间复杂度：
- 构造函数：O(N)，需要对 BST 完整遍历一遍。
- next() 和 hasNext()：O(1)。
空间复杂度：
- 存储 inOrderList：O(N)。
优点：
- 逻辑简单，实现容易。
缺点：
- 空间复杂度较高（需存储整个树所有节点值）。

解法 2：迭代 + 栈

思路：

基于中序遍历的特性，使用显式栈来模拟递归的调用栈。
- 中序遍历需要先处理左子树，直到找到最左端。
- 然后处理根节点，最后处理右子树。
在初始化时，将从根节点出发，沿左子树路径上的所有节点压入栈。
next() 时，从栈中弹出栈顶节点：
- 如果该节点有右子树，则对右子树执行相同操作（即将右子树路径上的所有左节点压入栈）。
hasNext() 简单检查栈是否为空。

模板代码：

class BSTIterator {private Stack<TreeNode> stack;public BSTIterator(TreeNode root) {stack = new Stack<>();pushLeft(root); // 初始化时沿左子树一路压栈}/** 将 root 节点的所有左子树节点压入栈 */private void pushLeft(TreeNode root) {while (root != null) {stack.push(root);root = root.left;}}/** 返回 BST 中的下一个最小值 */public int next() {TreeNode node = stack.pop();// 如果节点有右子树，对右子树重复压栈操作if (node.right != null) {pushLeft(node.right);}return node.val;}/** 判断是否还有下一个值 */public boolean hasNext() {return !stack.isEmpty();}
}

时间和空间复杂度：

时间复杂度：
- next()：均摊 O(1)。每个节点被压栈和弹栈各一次，总共为 O(N)。
- hasNext()：O(1)。
空间复杂度：
- 最坏情况下 O(H)，其中 H 是 BST 的高度（栈中最多存储完整的树高路径）。
优点：
- 空间效率更高，尤其是对于稀疏树或深度较大的 BST。
缺点：
- 实现略复杂。

解法 3：递归生成器

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

思路：

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

模板代码：

class BSTIterator {private Queue<Integer> queue; // 使用队列存储中序遍历结果public BSTIterator(TreeNode root) {queue = new LinkedList<>();inOrderTraversal(root);}/** 中序遍历，将节点值入队 */private void inOrderTraversal(TreeNode root) {if (root == null) return;inOrderTraversal(root.left);queue.offer(root.val);inOrderTraversal(root.right);}/** 返回 BST 中的下一个最小值 */public int next() {return queue.poll();}/** 判断是否还有下一个值 */public boolean hasNext() {return !queue.isEmpty();}
}

时间和空间复杂度：

时间复杂度：
- 构造函数：O(N)，一次构建中序遍历结果。
- next() 和 hasNext()：O(1)。
空间复杂度：
- 队列存储中序遍历结果，空间复杂度为 O(N)。
优点：
- 简单明了，易于理解。
缺点：
- 空间效率不佳，与解法 1 类似。

快速 AC 的建议

对于实际面试场景，建议优先选择 解法 2（迭代 + 栈）：
- 它时间和空间效率较高，是真正的「惰性遍历」。
- 运用了栈来模拟递归过程，是二叉树迭代问题的普适模板。
初始实现逻辑简单的情况下，可以实现 解法 1（存储序列）。
生成器法（解法 3）可以用于创建类似流式数据的接口实现。

经典变体题目

1. Binary Search Tree Preorder Iterator

问题： 按照「先序遍历」（根 -> 左 -> 右）的顺序实现类似的 Iterator。
解法：
- 使用栈来模拟先序遍历。
- 每次 next() 弹出栈顶节点，同时将 右子树 和 左子树（注意顺序）依次入栈。

class PreorderIterator {private Stack<TreeNode> stack;public PreorderIterator(TreeNode root) {stack = new Stack<>();if (root != null) stack.push(root);}public boolean hasNext() {return !stack.isEmpty();}public int next() {TreeNode node = stack.pop();if (node.right != null) stack.push(node.right); // 右子树先入栈if (node.left != null) stack.push(node.left);   // 左子树后入栈return node.val;}
}

2. Postorder Iterator

问题： 按照「后序遍历」（左 -> 右 -> 根）实现迭代器。
解法：
1. 利用双栈实现：第一栈模拟 root-right-left 的顺序，第二栈翻转为真正的后序遍历结果。
2. 使用一个布尔变量标记访问状态，写法略复杂。

class PostorderIterator {private Stack<TreeNode> stack1;private Stack<TreeNode> stack2;public PostorderIterator(TreeNode root) {stack1 = new Stack<>();stack2 = new Stack<>();if (root != null) stack1.push(root);while (!stack1.isEmpty()) {TreeNode node = stack1.pop();stack2.push(node);if (node.left != null) stack1.push(node.left);if (node.right != null) stack1.push(node.right);}}public boolean hasNext() {return !stack2.isEmpty();}public int next() {return stack2.pop().val;}
}

3. 二叉树层序遍历迭代器

问题： 按照「层序遍历」（逐层从上到下、从左到右）的顺序实现迭代器。
解法：
- 使用队列来模拟层序遍历。

class LevelOrderIterator {private Queue<TreeNode> queue;public LevelOrderIterator(TreeNode root) {queue = new LinkedList<>();if (root != null) queue.offer(root);}public boolean hasNext() {return !queue.isEmpty();}public int next() {TreeNode node = queue.poll();if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);return node.val;}
}