173. 二叉搜索树迭代器
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。
示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
My Answer
class BSTIterator {
private Stack
<TreeNode> stack
;
public BSTIterator(TreeNode root
) {
stack
= new Stack();
while(root
!=null
){
stack
.add(root
);
root
= root
.left
;
}
}
public int next() {
TreeNode t
= stack
.pop();
int val
= t
.val
;
t
= t
.right
;
while(t
!=null
){
stack
.add(t
);
t
= t
.left
;
}
return val
;
}
public boolean hasNext() {
return !stack
.isEmpty();
}
}
94. 二叉树的中序遍历
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
My Answer
class Solution {
public List
<Integer> inorderTraversal(TreeNode root
) {
List
<Integer> res
= new ArrayList();
Stack
<TreeNode> s
= new Stack();
while(root
!=null
|| !s
.isEmpty()){
while(root
!=null
){
s
.add(root
);
root
= root
.left
;
}
root
= s
.pop();
res
.add(root
.val
);
root
= root
.right
;
}
return res
;
}
}
