My Solution in C, using pointer to pointer


  • 0
    9
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct BSTIterator {
        struct TreeNode **stack;
        int top;
    };
    
    struct BSTIterator *bstIteratorCreate(struct TreeNode *root) {
        if(root == NULL)
            return NULL;
            
        struct BSTIterator *iter;
        struct TreeNode **stackTmp;
        struct TreeNode *p;
        
        iter->stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *)*6000);
        iter->top = -1;
        stackTmp = iter->stack;
        
        // 左节点全部进栈
        p = root;
        
        while(p != NULL)
        {
            iter->top ++;
            stackTmp[iter->top] = p;
            p = p->left;
        }
        
        return iter;
    }
    
    /** @return whether we have a next smallest number */
    bool bstIteratorHasNext(struct BSTIterator *iter) {
        if(iter == NULL)
            return false;
            
        if(iter->top >= 0)
            return true;
        else
            return false;
    }
    
    /** @return the next smallest number */
    int bstIteratorNext(struct BSTIterator *iter) {
        
        struct TreeNode **stackTmp;
        stackTmp = iter->stack;
        struct TreeNode *p;
        
        // 出栈一个元素
        int top = iter->top;
        int ret;
        p = stackTmp[top];
        iter->top --;
        ret = p->val;
        
        p = p->right;
        while(p != NULL)
        {
            iter->top ++;
            stackTmp[iter->top] = p;
            p = p->left;
        }
        
        return ret;
    }
    
    /** Deallocates memory previously allocated for the iterator */
    void bstIteratorFree(struct BSTIterator *iter) {
        if(iter != NULL)
        {
            struct TreeNode *stack = (iter->stack);
            free(stack);
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * struct BSTIterator *i = bstIteratorCreate(root);
     * while (bstIteratorHasNext(i)) printf("%d\n", bstIteratorNext(i));
     * bstIteratorFree(i);
     */

  • 0
    S

    I dont think its acceptable. you allocage 6000 items which is a "magic number" in development. This is the first place where I would look for bugs. you also have O(n) memory complexity. I would hate my job if someone asks me to support this code and not be able to rewrite it.

    Try to simplify or use existing solutions. Take a look on common iterative traversing and utilize that for current problem.
    Good luck.


  • 0
    9

    The problem is there is no existing Stack data structure in C, we have to realize a stack by using array. So I have to use a "magic number". In C++, you can use STL, such as "stack", "dequeue", this container will automatically expand its size. But for C programer, it is luxurious.

    Of course, I can use STL to realize the solution in C++. You can see it below. But I think this two codes are same in nature.

    As for memory complexity, I think the memory complexity is O(h).


  • 0
    9
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class BSTIterator {
    public:
    	stack<TreeNode*> stk;
    	int nextmin;
    	BSTIterator(TreeNode *root) {
    		while(root)
    		{
    			stk.push(root);
    			root = root->left;
    		}
    	}
    
    	/** @return whether we have a next smallest number */
    	bool hasNext() {
    		if(!stk.empty())
    		{
    			TreeNode* top = stk.top();
    			stk.pop();
    			nextmin = top->val;
    			TreeNode* cur = top->right;
    			if(cur)
    			{
    				stk.push(cur);
    				cur = cur->left;
    				while(cur)
    				{
    					stk.push(cur);
    					cur = cur->left;
    				}
    			}
    			return true;
    		}
    		else
    			return false;
    	}
    
    	/** @return the next smallest number */
    	int next() {
    		return nextmin;
    	}
    };
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = BSTIterator(root);
     * while (i.hasNext()) cout << i.next();
     */

  • 0
    S

    in C you still have pointers. so you can make list your own with push_back, pop_back and size. not a big deal. But my point was that you should allocate only what you need.


  • 0
    M

    It comes with the RunTime error !
    Somebody can explain why?


Log in to reply
 

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