[LeetCode]Binary Search Tree Iterator

BST中序遍历的迭代器，Inorder遍历iterative版本的好处就体现出来了，我们可以控制停在哪里，而recursive版本的就不好控制。这里我们要决定的是如何找到后继结点，分两种情况，一种是有右子树，那么我们找到右子树最小值即可。第二种是没有右子树，我们pop出栈顶的元素就是后继结点，至于为什么，我们在Binary Tree Preorder Traversal已经证明过这个问题。最后注意一下终止条件即可。

代码如下：

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

view raw Binary Search Tree Iterator.cpp hosted with ❤ by GitHub