深度优先遍历 DFS
解题思路
构造函数执行，递归调用 inorderDFS 将中序遍历的结果存储起来，并初始化 inx 用于记录访问的索引；
O(1)next 操作获取下一个元素；
O(1)hasNext 操作判断下一个元素是否存在；
复杂度
-
时间复杂度：构造函数初始化需要
O(n)的时间，其中 n 为树中节点的数量，随后每次调用只需要O(1)的时间； -
空间复杂度：
O(n)，因为需要保存中序遍历的全部结果；
代码实现
var BSTIterator = function (root) {
this.list = [];
this.inx = 0;
this.inorderDFS(root, this.list);
};
BSTIterator.prototype.next = function () {
return this.list[this.inx++];
};
BSTIterator.prototype.hasNext = function () {
return this.inx < this.list.length;
};
BSTIterator.prototype.inorderDFS = function (root, list) {
if (root === null) return;
this.inorderDFS(root.left, list);
list.push(root.val);
this.inorderDFS(root.right, list);
};
迭代（推荐）
解题思路
迭代时计算 next 节点，把递归转成迭代，基本想法就是用栈，自动压栈转成 手动压栈；
结合下图，实际访问节点的顺序是：
- 从 根节点12 开始一路到底遍历到所有左节点，路径保存到栈中；此时栈为 [12, 6, 5]；
- 弹出栈顶节点，即 叶子节点5；
- 下一个栈顶元素是 该叶子节点 的 根节点6；
- 然后把 该新的根节点的右子树9 一路到底遍历其所有左节点，栈为 [12, 9, 8, 7]；
- 继续运行下去，直到栈为空；
根据上面的遍历顺序，得出迭代的思路：
- 构造方法：一路到底，把根节点和它的所有左节点放到栈中；
- 调用 next() 方法：弹出栈顶的节点；如果它有右子树，则对右子树一路到底，把它和它的所有左节点放到栈中；
复杂度
-
时间复杂度：
O(1)； -
空间复杂度：
O(h)，h 为数的高度，因为栈中只保留了左节点，栈中元素最多的时候，就是树的高度；
代码实现
var BSTIterator = function (root) {
this.cur = root;
this.stack = [];
};
BSTIterator.prototype.next = function () {
// 1. 一路到底遍历到所有左节点，路径保存到栈中
while (this.cur) {
this.stack.push(this.cur);
this.cur = this.cur.left;
}
// 2. 弹出栈顶节点
this.cur = this.stack.pop();
const ret = this.cur.val;
// 3. 然后把 该新的根节点的右子树 一路到底遍历其所有左节点
this.cur = this.cur.right;
return ret;
};
BSTIterator.prototype.hasNext = function () {
return this.cur !== null || this.stack.length;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 701. 二叉搜索树中的插入操作
上一篇
评论
