binary_search_tree_iterator

hitzzc · hitzzc · commit 3397bd50b216 · 2016-10-15T22:03:54.000+08:00
diff --git a/README.md b/README.md
@@ -149,6 +149,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [169. Majority Element](https://github.com/hitzzc/go-leetcode/tree/master/majority_element)
 #### [171. Excel Sheet Column Number](https://github.com/hitzzc/go-leetcode/tree/master/excel_sheet_column_number)
 #### [172. Factorial Trailing Zeroes](https://github.com/hitzzc/go-leetcode/tree/master/factorial_trailing_zeroes)
+#### [173. Binary Search Tree Iterator](https://github.com/hitzzc/go-leetcode/tree/master/binary_search_tree_iterator)
 
 
 
diff --git a/binary_search_tree_iterator/binary_search_tree_iterator.cpp b/binary_search_tree_iterator/binary_search_tree_iterator.cpp
@@ -0,0 +1,38 @@
+#include <stack>
+
+struct TreeNode {
+	int val;
+	TreeNode *left;
+	TreeNode *right;
+	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+class BSTIterator {
+private:
+	stack<TreeNode*> stk;
+public:
+	BSTIterator(TreeNode *root) {
+		while (root != NULL){
+			stk.push(root);
+			root = root->left;
+		}
+	}
+	
+	/** @return whether we have a next smallest number */
+	bool hasNext() {
+		return !stk.empty();
+	}
+
+	/** @return the next smallest number */
+	int next() {
+		auto top = stk.top();
+		stk.pop();
+		int ret = top->val;
+		top = top->right;
+		while (top != NULL){
+			stk.push(top);
+			top = top->left;
+		}
+		return ret;
+	}
+};
