leecode 解题总结：173. Binary Search Tree Iterator

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>using namespace std;/*问题: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.分析:实现一个二叉搜索树的迭代器，通过next()函数返回其中下一个最小的元素。hasNext()和next()需要在O(1)时间，并且仅仅使用O(h)的内存，h是树的高度。二叉搜索树是：左子树中任意结点 < 根节点 < 右子树中任意结点举例:				12			4		     16		0      8     14    18	  -1  2   6  10  13 15 17 19	     1 3next就是记录当前最小元素的父节点就是next好像。如果当前结点没有左右孩子，返回当前结点的父节点如果当前结点有右孩子，返回该结点的右孩子中最左边的孩子注意：二叉查找树的特点是按照中序遍历，是已排序序列，寻找下一个元素，说白了，实际上就是中序遍历二叉树。只不过需要把遍历的过程限制一下，不是一次性遍历完，而是停留在某个结点，这个结点就是当前结点。那么所有的hasNext()条件就是栈不空或者当前结点不空next()，就是先获取下一个结点，然后输出下一个结点的值输入:1912 4 16 0 8 14 18 -1 2 6 10 13 15 17 19 N N 1 3输出:-1 0 1 2 3 4 6 8 10 12 13 14 15 16 17 18 19*/ struct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} };class BSTIterator {public:	//初始化的时候，先设置当前结点为根节点    BSTIterator(TreeNode *root) {        _current = root;    }    /** @return whether we have a next smallest number */    bool hasNext() {        if(!_nodes.empty() || _current)		{			return true;		}		else		{			return false;		}    }    /** @return the next smallest number */    int next() {		int result = 0;        while(!_nodes.empty() || _current)		{			//压入左孩子			if(_current)			{				_nodes.push(_current);				_current = _current->left;			}			//左孩子不存在，开始弹出栈顶元素			else			{				//当前元素就是左孩子，其值就是结果				TreeNode* node = _nodes.top();				result = node->val;				_nodes.pop();				_current = node->right;				break;			}		}		return result;    }PRivate:	TreeNode* _current;	stack<TreeNode*> _nodes;};TreeNode* buildBinaryTree(vector<string>& nums){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	int j = 0;	//结点i的孩子结点是2i,2i+1	vector<TreeNode*> nodes;	int value;	for(int i = 0 ; i < size ; i++)	{		//如果当前结点为空结点，自然其没有左右孩子结点		if("N" == nums.at(i))		{			nodes.push_back(NULL);			continue;		}		value = atoi(nums.at(i).c_str());		TreeNode* node = new TreeNode(value);		nodes.push_back(node);	}	//设定孩子结点指向,各个结点都设置好了，如果但钱为空结点，就不进行指向	for(int i = 1 ; i <= size ; i++)	{		if(NULL == nodes.at(i-1))		{			continue;		}		if(2 * i <= size)		{			nodes.at(i-1)->left = nodes.at(2*i - 1);		}		if(2*i + 1 <= size)		{			nodes.at(i-1)->right = nodes.at(2*i);		}	}	//设定完了之后，返回根节点	return nodes.at(0);}void deleteBinaryTree(TreeNode* root){	if(!root)	{		return;	}	if(NULL == root->left && NULL == root->right)	{		delete root;		root = NULL;	}	if(root)	{		deleteBinaryTree(root->left);		deleteBinaryTree(root->right);	}}void process(){	 vector<string> nums;	 string value;	 int num;	 vector<vector<string> > result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 TreeNode* root = buildBinaryTree(nums);		 BSTIterator i = BSTIterator(root);		 while (i.hasNext()) 		 {			 cout << i.next() << " ";		 }		 deleteBinaryTree(root);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}