[LeetCode] 173. Binary Search Tree Iterator

轉自LeetCode

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

<Solution>
這題的概念就是要做一個 in-order 輸出的 iterator

這邊使用一個 stack 來輔助

code 如下(參考資料)

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class BSTIterator {
	private:
	stack<TreeNode *> innerStack;
	public:
	BSTIterator(TreeNode *root) {
	while(root) {
	innerStack.push(root);
	root = root->left;
	}
	}
	/** @return whether we have a next smallest number */
	bool hasNext() {
	return !innerStack.empty();
	}
	/** @return the next smallest number */
	int next() {
	TreeNode *curN = innerStack.top();
	innerStack.pop();
	int nextVal = curN->val;
	if(curN->right) {
	curN = curN->right;
	while(curN) {
	innerStack.push(curN);
	curN = curN->left;
	}
	}
	return nextVal;
	}
	};
	/**
	* Your BSTIterator will be called like this:
	* BSTIterator i = BSTIterator(root);
	* while (i.hasNext()) cout << i.next();
	*/

view raw binarySearchTreeIterator_1.cpp hosted with ❤ by GitHub