利用stack完成树的中序遍历。stack沿着树一直向左走，当走不下去了。 如果结点有右孩子，那么读取top后放入右孩子。然后沿着右孩子向左走，一直走到没有左孩子了为止。 如果没有右孩子，直接读取top。
/** * 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 *> findNext;public: BSTIterator(TreeNode *root) { findNext.push(root); while(findNext.top()!=NULL) { TreeNode *temp=findNext.top(); findNext.push(temp->left); } findNext.pop(); } /** @return whether we have a next smallest number */ bool hasNext() { return (!findNext.empty()); } /** @return the next smallest number */ int next() { TreeNode *temp=findNext.top(); if(temp->right!=NULL) { findNext.pop(); findNext.push(temp->right); while(findNext.top()!=NULL) { TreeNode *temp=findNext.top(); findNext.push(temp->left); } findNext.pop(); } else { findNext.pop(); } return temp->val; }};/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */新闻热点
疑难解答
