题解 | #从上往下打印二叉树#

C语言的一种实现

typedef struct TreeNode Node;

#define Ele Node*

typedef struct Queue {
	Ele val;
	struct Queue* next;
}Queue;

typedef struct Queue_head {
	Queue* head;
	Queue* end;
}QQueue;

void AddQ(QQueue* P, Ele v)
{
	Queue* tmp = (Queue*)malloc(sizeof(Queue));
	if (!tmp )
	{
		printf("空间不够\n");
		return;

	}

	tmp->val = v;
	tmp->next = NULL;
    if(P->end)
        P->end->next=tmp;
    P->end = tmp;
	if (P->head == NULL)
		P->head = tmp;
}

Ele DeleteQ(QQueue* P)
{
	Queue* head;
	Ele tmp;
	if (P->head == NULL)
	{
		printf("队列空\n");
		return NULL;
	}
	head = P->head;
	if (P->head == P->end)
		P->head = P->end = NULL;
	else
		P->head = P->head->next;
	tmp = head->val;
	free(head);
	return tmp;
}


int* PrintFromTopToBottom(struct TreeNode* root, int* returnSize ) {
    int *a=(int*)malloc(sizeof(int)*1000);
    QQueue* Head = (QQueue*)malloc(sizeof(QQueue));
	Node* tmp;
    
	if (!root)
		return NULL;
	Head->end = NULL;
	Head->head = NULL;
    
    *returnSize=0;
	AddQ(Head, root);
	while (Head->head)
	{
		tmp = DeleteQ(Head);
        (*returnSize)++;
		a[(*returnSize)-1]=tmp->val;
		if (tmp->left)
			AddQ(Head, tmp->left);
		if (tmp->right)
			AddQ(Head, tmp->right);
	}
    
    return a;
}