Iterative solution in C with data structure "encapsulation"


  • 0
    A
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    
    
    struct node {
        struct TreeNode *treenode;
        struct node *next;
    };
    
    struct stack {
        struct node *top;
        int size;
    };
    
    void failIfNull(struct stack *stack){
      if(!stack) exit(-1);
    }
    
    int isEmpty(struct stack *stack){
      failIfNull(stack);
      if(stack->size==0) return 1;
      else return 0;
    }
    
    
    void newStack(struct stack **stack){
        *stack=malloc(sizeof(struct stack));
        (*stack)->size=0;
        (*stack)->top=NULL;
    }
    
    void printStack(struct stack *stack){
      struct node *node;
      if(!stack){
        printf("stack is null\n");
        return;
      }
      printf("size %d.  vals: ",stack->size);
      node=stack->top;
      while(node){
        if(!node->treenode){
          printf("storing NULL treenode!\n");
        }
        printf("%d ",node->treenode->val);
        node=node->next;
      }
      printf("\n");
    }
    struct TreeNode * pop(struct stack *stack){
      struct node stackRes;
      struct TreeNode *res;
      failIfNull(stack);
      if(isEmpty(stack))//implement a print error
        exit(-1);
      stackRes=*(stack->top);
      stack->top=stack->top->next;
      stack->size--;
      res=stackRes.treenode;
      return res;
    }
    
    void destroyStack(struct stack **stack){
        failIfNull(*stack);
        while(!isEmpty(*stack)){
            pop(*stack);
        }
        free(*stack);
        *stack=NULL;
    }
    
    
    void push(struct stack *stack, struct TreeNode *treenode){
        failIfNull(stack);
        struct node *newNode=malloc(sizeof(struct node));
        newNode->next=stack->top;
        newNode->treenode=treenode;
        stack->top=newNode;
        stack->size++;
        printf("pushed %d\nnusize %d\n", treenode->val,stack->size);
    }
    
    
    struct dynamicA {
      int maxSize;
      int *array;
    };
    
    void initA(struct dynamicA **A, int maxSize){
      *A=malloc(sizeof(struct dynamicA));
      (*A)->array=malloc((maxSize)*sizeof(int));
      (*A)->maxSize=maxSize;
    }
    
    /* void destroyA(struct dynamicA **A){ */
    /*   if(!A)return; */
    /*   if(*A && ( *A )->array) free(( *A )->array); */
    /*   if(*A) free(*A); */
    /*   *A=NULL; */
    /* } */
    
    void copyArray(int *fromA, int *toB, int n){
        int i;
        for(i=0;i<n;i++){
            toB[i]=fromA[i];
        }
    }
    
    void doubleA(struct dynamicA *A){
      int *B;
      B=malloc(2*A->maxSize*sizeof(int));
      copyArray(A->array,B,A->maxSize);
      free(A->array);
      A->array=B;
      A->maxSize=2*A->maxSize;
      printf("nusize %d \n",A->maxSize);
    }
    
    int inRangeA(struct dynamicA *A,int i){
        return i < A->maxSize;
    }
    
    void addItemA(struct dynamicA *A,int i,int val){
        if(!inRangeA(A,i)){
            doubleA(A);
            addItemA(A,i,val);
        }else{
            A->array[i] = val;
        }
    }
    
    
    int* preorderTraversal(struct TreeNode* root, int* returnSize) {
        struct dynamicA *A;
        struct stack *stack;
        newStack(&stack);
        int indexA=0;
        initA(&A,1);
        struct TreeNode *node=root;
        while(node){
          addItemA(A,indexA++,node->val);
          push(stack,node);
          node=node->left;
        }
        while(!isEmpty(stack)){
          node=pop(stack);
          if(node->right){
            node=node->right;
            while(node){
              addItemA(A,indexA++,node->val);
              push(stack,node);
              node=node->left;
            }
          }
        }
        destroyStack(&stack);
        *returnSize=indexA;
        return A->array;
    }
    

Log in to reply
 

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