【题目】

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.

【分析】

中序遍历

【代码】

/**********************************   日期：2015-01-03*   作者：SJF0115*   题目: 173.Binary Search Tree Iterator*   来源：https://oj.leetcode.com/problems/binary-search-tree-iterator/*   结果：AC*   来源：LeetCode*   博客：**********************************/#include 
    
     #include 
     
      #include 
      
       using namespace std;// 二叉查找树节点struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};// 插入void TreeInsert(TreeNode*& root,int val){    // 创建新节点    TreeNode* node = new TreeNode(val);    // 空树    if(root == NULL){        root = node;        return;    }//if    TreeNode *pre = NULL;    TreeNode *p = root;    // 寻找插入位置    while(p){        // 父节点        pre = p;        // 沿左子树方向下降        if(val < p->val){            p = p->left;        }//if        // 沿右子树方向下降        else{            p = p->right;        }//else    }//while    // 左子结点处插入    if(val < pre->val){        pre->left = node;    }//if    // 右子结点处插入    else{        pre->right = node;    }//else}// 创建二叉查找树TreeNode* TreeCreate(vector
       
         num){    TreeNode *root = NULL;    int len = num.size();    if(len == 0){        return root;    }//if    for(int i = 0;i < len;i++){        TreeInsert(root,num[i]);    }//for    return root;}class BSTIterator {public:    BSTIterator(TreeNode *root) {        TreeNode *p = root;        // 沿左子树下降        while(p){            s.push(p);            p = p->left;        }//while    }    /** @return whether we have a next smallest number */    bool hasNext() {        if(!s.empty()){            return true;        }//if        return false;    }    /** @return the next smallest number */    int next() {        TreeNode *p = NULL;        // 出栈        p = s.top();        s.pop();        int val = p->val;        // 转向右子树        if(p->right){            p = p->right;            // 沿左子树下降            while(p){                s.push(p);                p = p->left;            }//while        }//if        return val;    }private:    stack
        
          s;};int main() {    // -1代表NULL    vector
         
           num = {8,3,1,10,6,14,4,7,13}; TreeNode *root = TreeCreate(num); BSTIterator bSTIterator = BSTIterator(root); while(bSTIterator.hasNext()){ cout<
          
           <
          
         
        
       
      
     
    

【代码二】

class BSTIterator {    stack
    
      myStack;public:    BSTIterator(TreeNode *root) {        pushAll(root);    }    /** @return whether we have a next smallest number */    bool hasNext() {        return !myStack.empty();    }    /** @return the next smallest number */    int next() {        TreeNode *tmpNode = myStack.top();        myStack.pop();        pushAll(tmpNode->right);        return tmpNode->val;    }private:    void pushAll(TreeNode *node) {        for (; node != NULL; myStack.push(node), node = node->left);    }};