My code:
import java.util.ArrayList;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
private ArrayList<Integer> bst = null;
private int index;
public BSTIterator(TreeNode root) {
bst = new ArrayList<Integer>();
if (root == null) {
index = Integer.MAX_VALUE;
return;
}
this.index = 0;
inOrder(root, bst);
}
private void inOrder(TreeNode root, ArrayList<Integer> bst) {
if (root.left != null)
inOrder(root.left, bst);
bst.add(root.val);
if (root.right != null)
inOrder(root.right, bst);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if (this.index < bst.size())
return true;
else
return false;
}
/** @return the next smallest number */
public int next() {
return bst.get(index++);
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
My test result:
现在刷题，做完之后，都忘记这道题目是干什么的了。。。是立刻就忘记。。。
这道题目，挺新颖的。我自己的做法，就是生成一个arraylist，按照inorder的顺序。
这些正好今天上课全部讲到了。
然后每次需要最小的，就取出index，并且往前进一格。
判断hasNext(), 就判断index是否 >= arrayList.size() 就行了。
然后有点麻烦的地方，就是如果root = null。
怎么办。
然后我学习到了，
原来构造函数中，也可以使用return
**
总结： inorder BST 出来的数列是从小到大排列的。 构造函数中可以使用 return
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
Stack<TreeNode> s;
public BSTIterator(TreeNode root) {
s = new Stack<TreeNode>();
while (root != null) {
s.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !s.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode temp = s.pop();
TreeNode root = temp.right;
while (root != null) {
s.push(root);
root = root.left;
}
return temp.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
题目的要求是，
时间， 平均，O(1)
空间， O(h)
所以我的原做法，空间复杂度达到了O(n)
现在采用非递归的做法做。将左侧的都压到栈中。空间复杂度就达到了O(h)
然后，每次弹出一个，即为返回值。
同时需要将它的右子树的左侧一边的所有结点全部压到栈中。空间复杂度最恶劣的化可以达到O(n)
但是，从平均来看，访问n个元素，时间复杂度是O(n)
所以对于每一个next操作，复杂度平均下来，是O(1)
就是这个O(1) 卡住了我。。。
参考网页：
http://www.programcreek.com/2014/04/leetcode-binary-search-tree-iterator-java/
Anyway, Good luck, Richardo!
My code:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
Stack<TreeNode> st = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
st.push(curr);
curr = curr.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !st.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode ret = st.pop();
TreeNode curr = ret;
if (curr.right != null) {
curr = curr.right;
while (curr != null) {
st.push(curr);
curr = curr.left;
}
}
return ret.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
自己写了出来。主要就是 average O(1)
Anyway, Good luck, Richardo! -- 09/06/2016
