C solution using self-implemented stack


  • 0
    C
    typedef struct stack {
        void         *c;
        struct stack *next;
    } Stack;
    
    void stackCreate(Stack **ptop)
    {
        *ptop = NULL;
    }
    
    void push(Stack **ptop, void *c)
    {
        Stack   *tmp;
        
        tmp = malloc(sizeof *tmp);
        tmp->c = c;
        tmp->next = *ptop;
        
        *ptop = tmp;
    }
    
    void pop(Stack **ptop, void **c)
    {
        Stack   *tmp;
        
        if (! *ptop) return;
        
        tmp = *ptop;
        *c = tmp->c;
        *ptop = (*ptop)->next;
        //free(tmp);
    }
    
    int stackEmpty(Stack **ptop)
    {
       return *ptop == NULL; 
    }
    
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    struct BSTIterator {
        struct TreeNode *root;
        struct TreeNode *curr;
        Stack           *stack;
    };
    
    struct BSTIterator *bstIteratorCreate(struct TreeNode *root) {
        struct BSTIterator  *iter;
        
        iter = malloc(sizeof *iter);
        iter->curr = iter->root = root;
        stackCreate(&iter->stack);
        
        while (iter->curr) {
            push(&iter->stack, iter->curr);
            iter->curr = iter->curr->left;
        }
        
        return iter;
    }
    
    /** @return whether we have a next smallest number */
    bool bstIteratorHasNext(struct BSTIterator *iter) {
        return !stackEmpty(&iter->stack);
    }
    
    /** @return the next smallest number */
    int bstIteratorNext(struct BSTIterator *iter) {
        int     val;
        
        pop(&iter->stack, &iter->curr);
        val = iter->curr->val;
        iter->curr = iter->curr->right;
        while (iter->curr) {
            push(&iter->stack, iter->curr);
            iter->curr = iter->curr->left;
        }
        
        return val;
    }
    
    /** Deallocates memory previously allocated for the iterator */
    void bstIteratorFree(struct BSTIterator *iter) {
        if (iter) free(iter);
    }
    
    /**
     * Your BSTIterator will be called like this:
     * struct BSTIterator *i = bstIteratorCreate(root);
     * while (bstIteratorHasNext(i)) printf("%d\n", bstIteratorNext(i));
     * bstIteratorFree(i);
     */
    

Log in to reply
 

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