199. Binary Tree Right Side View

类似level order,只是保存每层的最后一个节点：
if(i == size-1){
ret = realloc(ret, (returnSize+1)sizeof(int));
ret[*returnSize] = node->val;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
struct queue{
    struct ListNode * dummy;
    struct ListNode * last;

};

struct queue * init_queue()
{
    struct queue * q = calloc(1, sizeof(struct queue));
    q->dummy = calloc(1, sizeof(struct ListNode));
    q->last = q->dummy;

    return q;

}

void enqueue(struct queue *q, void * val){
    struct ListNode * node = calloc(1, sizeof(struct ListNode));
    node->val = (int)val;
    node->next = NULL;
    q->last->next = node;
    q->last = node;
}

void * dequeue(struct queue * q)
{
    if(q->dummy->next){
        void * ret = (void *)q->dummy->next->val;
        if(q->last == q->dummy->next)
            q->last = q->dummy;
        q->dummy->next = q->dummy->next->next;


        return ret;
    }else
        return NULL;
}

int queue_size(struct queue *q)
{
    int i = 0;
    struct ListNode * p = q->dummy->next;
    while(p){
        p = p->next;
        i++;
    }
    return i;
}
int* rightSideView(struct TreeNode* root, int* returnSize) {  

    if(root == NULL)
        return NULL;
    struct queue * q = init_queue();
    enqueue(q, (void *)root);
    *returnSize = 0;
    int *ret = calloc(*returnSize, sizeof(int));
    

    while(q->dummy->next != NULL){
        

        
        int size = queue_size(q);

        
        for(int i = 0; i < size; i++){
            struct TreeNode* node = (struct TreeNode *)dequeue(q);
            //printf("%d  ", node->val);
            if(node->left)
                enqueue(q, (void *)node->left);
            if(node->right)
                enqueue(q, (void *)node->right);
            if(i == size-1){
                ret = realloc(ret, (*returnSize+1)*sizeof(int));
                ret[*returnSize] = node->val;
            }

        }
        *returnSize +=1;


    }

    return ret;
}