中山网站建设文化咨询百度惠生活商家入驻

如果直接用递归中序遍历存到数组中，然后输出，这样的时间复杂度是O(n)

为了只用O(h)的空间，我们采用非递归迭代策略。

思路：

能往左走就往左走，边走边入栈，直到不能走，弹出栈里元素往右走，重复之前操作。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class BSTIterator {public:stack<TreeNode*> st;TreeNode* cur;BSTIterator(TreeNode* root) {cur = root;}/** @return the next smallest number */int next() {while(cur != NULL){st.push(cur);cur = cur -> left;}cur = st.top();st.pop();int val = cur->val;cur = cur->right;return val;}/** @return whether we have a next smallest number */bool hasNext() {return cur != NULL || !st.empty();}
};/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator* obj = new BSTIterator(root);* int param_1 = obj->next();* bool param_2 = obj->hasNext();*/