尧图网站建设 
题目分析LeetCode 173. 二叉搜索树迭代器要求实现一个二叉搜索树BST的迭代器需满足以下核心条件BSTIterator(TreeNode root)初始化迭代器指针初始指向一个不存在于 BST 中的、比任何元素都小的数。boolean hasNext()如果向指针右侧遍历存在数字返回 true否则返回 false。int next()将指针右移返回指针位置的数字。进阶要求 next() 和 hasNext() 的均摊时间复杂度为 O(1)且使用 O(h) 的内存h 为树的高度。核心思路二叉搜索树的中序遍历结果是升序排列的因此迭代器的本质就是实现一个受控的中序遍历。如果直接把中序遍历结果全部存入数组虽然 next() 是 O(1)但初始化需要 O(n) 时间和 O(n) 空间不满足进阶要求。最优解使用栈模拟中序遍历的迭代过程。初始化时将根节点及其所有左子节点压入栈中此时栈顶就是最小的元素。每次调用 next() 时弹出栈顶元素即当前最小值如果该节点有右子树则将右子树的所有左子节点压入栈。hasNext() 只需判断栈是否为空。这样每个节点最多只会被压入和弹出栈一次均摊下来 next() 的时间复杂度是 O(1)空间复杂度为栈的深度 O(h)。Java 实现/**Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}*/class BSTIterator {private Deque stack;public BSTIterator(TreeNode root) {stack new ArrayDeque();// 初始化将根节点及所有左子节点压入栈pushLeft(root);}/**返回下一个最小的数字均摊时间复杂度 O(1)*/public int next() {// 弹出栈顶当前最小节点TreeNode node stack.pop();// 如果该节点有右子树将右子树的所有左子节点压入栈if (node.right ! null) {pushLeft(node.right);}return node.val;}/**判断是否还有下一个数字时间复杂度 O(1)*/public boolean hasNext() {return !stack.isEmpty();}/**辅助方法将节点及其所有左子节点压入栈*/private void pushLeft(TreeNode node) {while (node ! null) {stack.push(node);node node.left;}}}/**Your BSTIterator object will be instantiated and called as such:BSTIterator obj new BSTIterator(root);int param_1 obj.next();boolean param_2 obj.hasNext();*/复杂度分析维度 复杂度 说明初始化时间 O(h) 只需要遍历从根到最左叶子的路径next() 均摊时间 O(1) 每个节点最多入栈和出栈各一次总操作次数为 2n均摊每次 O(1)hasNext() 时间 O(1) 只需判断栈是否为空空间复杂度 O(h) 栈中最多同时存储 h 个节点树的高度执行过程图解假设 BST 如下7/3 15/9 20初始化 将 7 → 3 压入栈栈状态[3, 7]栈顶在左调用 操作 返回值 栈状态变化next() 弹出 33 无右子树 3 [7]hasNext() 栈非空 true [7]next() 弹出 77 有右子树 15将 15 → 9 压入栈 7 [9, 15]next() 弹出 99 无右子树 9 [15]next() 弹出 1515 有右子树 20将 20 压入栈 15 [20]next() 弹出 2020 无右子树 20 []hasNext() 栈为空 false []输出序列3, 7, 9, 15, 20 ✅ 正是中序遍历的升序结果。面试延伸如果面试官追问可以补充说明为什么用 ArrayDeque 而不是 Stack Stack 是遗留类继承自 Vector带有同步开销且性能较差现代 Java 推荐使用 Deque 接口实现栈操作。如果要求实现 prev() 方法双向迭代器怎么办 可以维护两个栈一个用于 next()中序遍历一个用于 prev()反向中序遍历类似双指针思想。** Morris 遍历能做到 O(1) 空间吗** 理论上可以但 Morris 遍历会临时修改树的结构 threading 在多线程或不可变树场景下不安全面试中一般不推荐作为首选方案。这道题是 BST 高频考点和验证二叉搜索树BST 中第 K 小的元素属于同一类中序遍历变形需要我顺带把这两道题的思路也整理一下吗 千问 LeetCode 173. 二叉搜索树迭代器 Java实现
题目分析LeetCode 173. 二叉搜索树迭代器要求实现一个二叉搜索树BST的迭代器需满足以下核心条件BSTIterator(TreeNode root)初始化迭代器指针初始指向一个不存在于 BST 中的、比任何元素都小的数。boolean hasNext()如果向指针右侧遍历存在数字返回 true否则返回 false。int next()将指针右移返回指针位置的数字。进阶要求 next() 和 hasNext() 的均摊时间复杂度为 O(1)且使用 O(h) 的内存h 为树的高度。核心思路二叉搜索树的中序遍历结果是升序排列的因此迭代器的本质就是实现一个受控的中序遍历。如果直接把中序遍历结果全部存入数组虽然 next() 是 O(1)但初始化需要 O(n) 时间和 O(n) 空间不满足进阶要求。最优解使用栈模拟中序遍历的迭代过程。初始化时将根节点及其所有左子节点压入栈中此时栈顶就是最小的元素。每次调用 next() 时弹出栈顶元素即当前最小值如果该节点有右子树则将右子树的所有左子节点压入栈。hasNext() 只需判断栈是否为空。这样每个节点最多只会被压入和弹出栈一次均摊下来 next() 的时间复杂度是 O(1)空间复杂度为栈的深度 O(h)。Java 实现/**Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}*/class BSTIterator {private Deque stack;public BSTIterator(TreeNode root) {stack new ArrayDeque();// 初始化将根节点及所有左子节点压入栈pushLeft(root);}/**返回下一个最小的数字均摊时间复杂度 O(1)*/public int next() {// 弹出栈顶当前最小节点TreeNode node stack.pop();// 如果该节点有右子树将右子树的所有左子节点压入栈if (node.right ! null) {pushLeft(node.right);}return node.val;}/**判断是否还有下一个数字时间复杂度 O(1)*/public boolean hasNext() {return !stack.isEmpty();}/**辅助方法将节点及其所有左子节点压入栈*/private void pushLeft(TreeNode node) {while (node ! null) {stack.push(node);node node.left;}}}/**Your BSTIterator object will be instantiated and called as such:BSTIterator obj new BSTIterator(root);int param_1 obj.next();boolean param_2 obj.hasNext();*/复杂度分析维度 复杂度 说明初始化时间 O(h) 只需要遍历从根到最左叶子的路径next() 均摊时间 O(1) 每个节点最多入栈和出栈各一次总操作次数为 2n均摊每次 O(1)hasNext() 时间 O(1) 只需判断栈是否为空空间复杂度 O(h) 栈中最多同时存储 h 个节点树的高度执行过程图解假设 BST 如下7/3 15/9 20初始化 将 7 → 3 压入栈栈状态[3, 7]栈顶在左调用 操作 返回值 栈状态变化next() 弹出 33 无右子树 3 [7]hasNext() 栈非空 true [7]next() 弹出 77 有右子树 15将 15 → 9 压入栈 7 [9, 15]next() 弹出 99 无右子树 9 [15]next() 弹出 1515 有右子树 20将 20 压入栈 15 [20]next() 弹出 2020 无右子树 20 []hasNext() 栈为空 false []输出序列3, 7, 9, 15, 20 ✅ 正是中序遍历的升序结果。面试延伸如果面试官追问可以补充说明为什么用 ArrayDeque 而不是 Stack Stack 是遗留类继承自 Vector带有同步开销且性能较差现代 Java 推荐使用 Deque 接口实现栈操作。如果要求实现 prev() 方法双向迭代器怎么办 可以维护两个栈一个用于 next()中序遍历一个用于 prev()反向中序遍历类似双指针思想。** Morris 遍历能做到 O(1) 空间吗** 理论上可以但 Morris 遍历会临时修改树的结构 threading 在多线程或不可变树场景下不安全面试中一般不推荐作为首选方案。这道题是 BST 高频考点和验证二叉搜索树BST 中第 K 小的元素属于同一类中序遍历变形需要我顺带把这两道题的思路也整理一下吗