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 的最大索引。
模板代码：
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
[*]题目： 按照「后序遍历」（左 -> 右 -> 根）实现迭代器。
[*]解法：
[*]利用双栈实现：第一栈模仿 root-right-left 的顺序，第二栈翻转为真正的后序遍历结果。
[*]使用一个布尔变量标记访问状态，写法略复杂。
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;
}
}
总结
[*]核心解法：
[*]解法 2（迭代 + 栈）是最核心的技巧，适用于惰性遍历场景，推荐用于实际使用和口试。
[*]经典变种：
[*]各类二叉树遍历模式（中序、先序、后序、层序）的迭代器实现都可以通过栈或队列模仿递归来实现。
[*]快速 AC 的关键：
[*]掌握递归和迭代的转换，机动选择数据布局（栈或队列）。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]