144 binary tree preorder traversal

根节点先入栈，然后弹出的同时，把右孩子入栈，然后左孩子（方便先访问保存左孩子）

struct Stack{
    struct ListNode  * dummy;
};

void push(struct Stack * s, int val)
{
    struct ListNode * node = calloc(1, sizeof(struct ListNode));
    node->val = val;
    node->next = s->dummy->next;
    s->dummy->next = node;
}

int pop(struct Stack *s)
{

    struct ListNode * p = s->dummy->next;
    if(p){
        s->dummy->next = p->next;
        int ret = p->val;

        free(p);
        return ret;
    }else{
        printf("empty stack\n");
        return -1;

    }
}

struct Stack * init_stack()
{
    struct Stack *s;
    s = calloc(1, sizeof(struct Stack));
    s->dummy = calloc(1, sizeof(struct ListNode));

    return s;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
    struct Stack * s1 = init_stack();
    //struct Stack * s2 = init_stack();
    if(root == NULL)
        return NULL;
    push(s1,(int)root);
    *returnSize = 0;
    int *ret = calloc(*returnSize, sizeof(int));
    
    while(s1->dummy->next){
        struct TreeNode *node = (struct TreeNode *)pop(s1);
        
        ret = realloc(ret, (*returnSize+1)*sizeof(int));
        ret[*returnSize] = node->val;
        *returnSize +=1;
        
        if(node->right)
            push(s1, (int)node->right);
        if(node->left)
            push(s1, (int)node->left);

        

    }



    return ret;
}
``