本文共 2860 字，大约阅读时间需要 9 分钟。

树的遍历主要是四种：前序、中序遍历、后序、分层遍历。前三种一般用递归的方法，而递归方法都会用到堆栈；分层遍历需要用到队列，队列的实现也是不唯一的，根据需要建立自己的结构。这道题具体的方法是，先将根入栈，记录size=1（我的size在队列中），出栈生成需要的数组，size = 0；再将他的左右儿子入栈，size...一直循环到size=0，也就是不再有入栈且完全出栈的时候（描述不好。。）。

这道题对题目的理解很重要：leetcode中 形参为（整形）指针，一般是要传回的整形；形参为二维指针，要传回数组，而前一个整形正是这个数组的大小。

/*** Return an array of arrays of size *returnSize. 返回二维数组的大小* The sizes of the arrays are returned as *columnSizes array.   *columnSizes是一个数组，注意，不是columnSizes* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/

这道题参考了别人的答案，但能做出来很开心啊，加油！

* Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*** 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().*/#include
   
    #include
    
     #define ElementType struct TreeNodetypedef struct QueueRecord *Queue;typedef struct TreeNode *Tree;struct TreeNode {	int val;	struct TreeNode *left;	struct TreeNode *right;};//创建一个队列--链表实现struct QueueRecord{	int size;	ElementType *element;	Queue next;};//省略空间检测Queue Initialize(){	Queue H = (Queue)malloc(sizeof(struct QueueRecord));	H->size = 0;	H->element = NULL;	H->next = NULL;	return H;}void Enqueue(ElementType *node, Queue Q){	Queue temp;	temp = (Queue)malloc(sizeof(struct QueueRecord));	Q->size++;	temp->element = node;	temp->next = Q->next;	Q->next = temp;}Queue Dequeue(Queue Q){	Queue temp = Q;	Queue tem;	if (temp->next)	{		while (temp->next->next != NULL)		{			temp = temp->next;		}	}	tem = temp->next;	temp->next = NULL;	Q->size--;	return tem;}//*returnSize 返回数组大小，*columnSizes 是返回数组内部数组的大小的数组int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {	if (root == NULL)		return NULL;	Queue Q = Initialize();	Enqueue(root, Q);	int lever = 4;	int **Ret = (int**)malloc(lever * sizeof(int*));	int size;	int *column;	int *colsize = (int*)malloc(lever*sizeof(int));	Queue out;	int j = 0;	while (Q->size != 0)	{		size = Q->size;		int i = 0;		column = (int*)malloc(size*sizeof(int));				colsize[j] = size;		do		{			out = Dequeue(Q);			column[i++] = out->element->val;			if (out->element->left)			{				Enqueue(out->element->left,Q);			}			if (out->element->right)			{				Enqueue(out->element->right, Q);			}		} while (--size);		if (j >= lever-1)		{			lever = lever << 1;			Ret = (int**)realloc(Ret, lever*sizeof(int*));//重新分配地址空间			colsize = (int*)realloc(colsize, lever*sizeof(int*));		}		Ret[j++] = column;				}	*columnSizes = colsize;	*returnSize = j;	return Ret;}void main(){	Tree T = (Tree)malloc(1 * sizeof(struct TreeNode));	T->val = 1;	T->left = NULL;	T->right = NULL;	int **c = (int**)malloc(1 * sizeof(int*));;	int *r = (int *)malloc(sizeof(int));	int ** ret = levelOrder(T, c, r);	getchar();}
    
   

转载地址：http://jhovi.baihongyu.com/