这段代码，在后面跑测试用例时，出现了stack-overflow，但是原因还不清楚。
问题如下：
二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
因为要输出一个二维数组，那么我需要定义一个两重链表，具体定义如下：
/* 链表节点 用于存储输出结果 */ struct listNode { int val; struct listNode *next; }; struct list { int count; struct listNode *head; struct listNode *tail; struct list *next; }; struct list_list { int count; struct list *head; struct list *tail; };
链表的一些操作如下：
void init_list(struct list *l) { l->count = 0; l->head = NULL; l->tail = NULL; l->next = NULL; } void init_list_list(struct list_list *l) { l->count = 0; l->head = NULL; l->tail = NULL; } void add_new_node(struct list *l, struct listNode *node) { if (!l->head) { l->head = node; l->tail = node; l->count = 1; return; } l->tail->next = node; l->tail = node; l->count++; } void add_new_list(struct list_list *ll, struct list *l) { if (ll->head == NULL) { ll->head = l; ll->tail = l; ll->count = 1; return; } ll->tail->next = l; ll->tail = l; ll->count++; }
链表创建如下：
struct list_list * create_list_list() { struct list_list *ll = malloc(sizeof(struct list_list)); if (ll) { init_list_list(ll); } return ll; } struct list * create_list() { struct list *l = malloc(sizeof(struct list)); if (l) { init_list(l); } return l; }
另外需要定义一个队列，用于存放每个树节点
/* 队列节点，用于存储已经遍历过的根节点 */ struct queue_node { void *entry; struct queue_node *next; }; struct queue { struct queue_node *front; struct queue_node *rear; };
队列的一些简单操作实现如下：
/* 队列节点，用于存储已经遍历过的根节点 */ struct queue_node { void *entry; struct queue_node *next; }; struct queue { struct queue_node *front; struct queue_node *rear; }; void init_queue(struct queue *q) { q->front = NULL; q->rear = NULL; } void queue_push(struct queue *q, void *np) { struct queue_node *node = malloc(sizeof(struct queue_node)); node->entry = np; node->next = NULL; if (q->rear == NULL) { q->rear = node; q->front = node; } else { q->rear->next = node; q->rear = node; } } void *queue_pop(struct queue *q) { struct queue_node *np = q->front; void *entry = NULL; if (np) { entry = np->entry; if (np->next == NULL) q->rear = NULL; q->front = np->next; free(np); } return entry; }
struct queue * create_queue() { struct queue *q = malloc(sizeof(struct queue)); if (q) { init_queue(q); } return q; }
主函数的具体实现思想为，遍历根节点，将其存入队列中，然后在队列中插入一个flag标记，之后进入一个while循环，循环中，每次从队列中取出一个成员，将该成员存入到用于输出的二层链表中，然后判断其左右孩子是否为空，不为空，则其左右孩子入队列。然后再循环，当从队列中取出的是flag标志后，并且队列中还没空，那么就在这个队列中再插入一个flag标志，表示这一层的遍历结束，可以输出这一层的链表。如此循环，直到所有节点都入队列，读到最后一个flag标记，并且队列为空，那么整个遍历流程结束。后面就是把二层链表输出成一个二维数组。
代码如下：
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){ struct list_list *ll; struct list *subList; struct listNode *head; struct queue *q; struct TreeNode *pNode = NULL; struct listNode *newnode = NULL; int **r; int *subr; struct list *l; int i,j; int *size; int *resize; if (!root || !returnSize || !returnColumnSizes) return; q = create_queue(); ll = create_list_list(); l = create_list(); add_new_list(ll, l); queue_push(q, (void*)root); queue_push(q, FINISH_FALG); while (q->front != NULL) { pNode = (struct TreeNode *)queue_pop(q); if (pNode == FINISH_FALG) { if (q->front == NULL) break; /* 创建新的链表，在总链表中插入新的链表 */ l = create_list(); add_new_list(ll, l); /* 在当前队列中再插入一个终结标志 */ queue_push(q, FINISH_FALG); continue; } /* 该节点插入到当前链表中 */ newnode = create_node(pNode->val); add_new_node(l, newnode); /* 将当前节点的左右孩子加入队列中 */ if (pNode->left != NULL) { queue_push(q, (void*)pNode->left); } if (pNode->right != NULL) { queue_push(q, (void*)pNode->right); } } r = (int **)malloc(sizeof(int *) * ll->count); resize = (int *)malloc(sizeof(int *) * ll->count); subList = ll->head; while(subList && i < ll->count) { subr = (int *)malloc(sizeof(int) * subList->count); head = subList->head; j = 0; while(head && j < subList->count) { subr[j] = head->val; j++; head = head->next; } resize[i] = subList->count; r[i] = subr; i++; subList = subList->next; } *returnSize = ll->count; *returnColumnSizes = resize; return r; }