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:
現(xiàn)在刷題，做完之后功舀，都忘記這道題目是干什么的了萍倡。。辟汰。是立刻就忘記列敲。阱佛。。
這道題目戴而，挺新穎的凑术。我自己的做法，就是生成一個arraylist所意，按照inorder的順序淮逊。
這些正好今天上課全部講到了。
然后每次需要最小的扁眯，就取出index壮莹，并且往前進(jìn)一格。
判斷hasNext(), 就判斷index是否 >= arrayList.size() 就行了姻檀。
然后有點麻煩的地方命满，就是如果root = null。
怎么辦绣版。
然后我學(xué)習(xí)到了胶台，
原來構(gòu)造函數(shù)中，也可以使用return
**
總結(jié)： inorder BST 出來的數(shù)列是從小到大排列的杂抽。 構(gòu)造函數(shù)中可以使用 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)
所以我的原做法，空間復(fù)雜度達(dá)到了O(n)
現(xiàn)在采用非遞歸的做法做杭朱。將左側(cè)的都壓到棧中阅仔。空間復(fù)雜度就達(dá)到了O(h)
然后弧械，每次彈出一個八酒，即為返回值。
同時需要將它的右子樹的左側(cè)一邊的所有結(jié)點全部壓到棧中刃唐⌒呙裕空間復(fù)雜度最惡劣的化可以達(dá)到O(n)
但是，從平均來看画饥，訪問n個元素衔瓮，時間復(fù)雜度是O(n)
所以對于每一個next操作，復(fù)雜度平均下來抖甘，是O(1)
就是這個O(1) 卡住了我热鞍。。。
參考網(wǎng)頁：
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
