I had implemented with stack instead of recursion.But there is a problem.


  • 0
    B

    I had implemented with stack instead of recursion.But there is a problem ,say"Runtime Error last excuted input:{2,1,3}" .Is there any problem you find?

    this is my code:

    #include <iostream>
    #include <stack>
    using namespace std;
    class BSTIterator {
    public:
        stack<TreeNode*> stk;
    	TreeNode *head,*pre;
    	BSTIterator(TreeNode *root) {
    	    	head = NULL;
    	    	pre =NULL;
    	    	turntoStack(root);
    	    }
    	   void turntoStack(TreeNode *root){
    	    	if(root==NULL) return;
    		    stk.push(root);
    	    	root = root->left;
    	    	while(!stk.empty() || root ){
    
    	    		while(root){
    	    			stk.push(root);
    	    			root = root->left;
    	    		}
    
    	    		TreeNode *tNode = stk.top();
    
    	    		if(head == NULL)
    	    			head = tNode;
    
    	    		if(pre == NULL) pre = tNode;
    	    		else {
    	    			pre->right = tNode;
    	    			pre = tNode;
    	    		}
    	    		stk.pop();
    	    		if(tNode->right)
    	    			{
    	    				root = tNode ->right;
    	    			}
    	    	}
    	    }
    	   /** @return whether we have a next smallest number */
    	 bool hasNext() {
    
    	    	return head != NULL;
    	 }
    
    	    /** @return the next smallest number */
    	  int next() {
    	    	TreeNode *t= head;
    	    	head=head->right;
    	    	return t->val;
    	  }
    };

  • 0
    C

    Strange... I tried your code in my test-stub and for all combinations of 1,2,3 in a search-tree it gives correct results.


  • 0
    B

    me,too . I'm confused.Maybe the problem is that my code does not meet the "next() and hasNext() should run in average O(1) time and uses O(h) memory"


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.