AlgoViz Lab交互式算法学习Algorithms first
二叉搜索树迭代器 · 交互式算法学习
实现按升序迭代二叉搜索树。
#173 · 二叉树
二叉搜索树迭代器
Binary Search Tree Iterator
root = [7,3,15,null,null,9,20]树 / 图3 个关键状态
步骤 1初始化压入 7、3 的左链。
stack=[7,3]推荐
受控中序栈
时间
next 均摊 O(1)空间 O(h)栈只保存尚未访问的左链；弹出后压入右子树左链。
1class BSTIterator {2 constructor(root) {3 this.s = [];4 this.pushLeft(root)5 }6 pushLeft(n) {7 while (n) {8 this.s.push(n);9 n = n.left10 }11 }12 next() {13 const n = this.s.pop();14 this.pushLeft(n.right);15 return n.val16 }17 hasNext() {18 return this.s.length > 019 }20}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val = val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {10 * this.val = val;11 * this.left = left;12 * this.right = right;13 * }14 * }15 */16class BSTIterator {17 private int cur = 0;18 private List<Integer> vals = new ArrayList<>();19 20 public BSTIterator(TreeNode root) {21 inorder(root);22 }23 24 public int next() {25 return vals.get(cur++);26 }27 28 public boolean hasNext() {29 return cur < vals.size();30 }31 32 private void inorder(TreeNode root) {33 if (root != null) {34 inorder(root.left);35 vals.add(root.val);36 inorder(root.right);37 }38 }39}40 41/**42 * Your BSTIterator object will be instantiated and called as such:43 * BSTIterator obj = new BSTIterator(root);44 * int param_1 = obj.next();45 * boolean param_2 = obj.hasNext();46 */交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
二叉搜索树迭代器 · 解法对比
实现按升序迭代二叉搜索树。
- 测试用例
root = [7,3,15,null,null,9,20]- 题目分类
- 二叉树
- 解法对比
- 2
预先完整中序遍历
构造时把中序结果存入数组，next 读取下一个。
- 时间
初始化 O(n)- 空间
O(n)
受控中序栈
栈只保存尚未访问的左链；弹出后压入右子树左链。
- 时间
next 均摊 O(1)- 空间
O(h)