博客

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:

给定二叉树: [3,9,20,null,null,15,7]

返回其层次遍历结果：

[

[3],

[9,20],

[15,7]

]

/** * 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 
* *returnColumnSizes array. 
* * Note: Both returned array and 
* *columnSizes array must be malloced, assume caller calls free(). 
* */
#define MAXSIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
 if(NULL == root)    
 {        
 	*returnSize = 0;        
	 return NULL;    
 }
 struct TreeNode *queue[MAXSIZE] = {0};     //申请队列
 int head = 0, tail = 0;          	   //定义头尾指针
 int **res = (int**)malloc(sizeof(int*)*MAXSIZE);//申请二维数组    *returnColumnSizes = (int*)malloc(sizeof(int)*MAXSIZE);//申请一维数组    queue[tail++] = root;//将根节点入队
*returnSize = 0;
 while(head < tail)    
 {        
 int size = (tail - head)%MAXSIZE;获取对内元素个数        
 (*returnColumnSizes)[*returnSize] = size; //一维数组中存放元素个数
 res[*returnSize] = (int*)malloc(sizeof(int)*size);//依据元素个数开辟行数组              
	 for(int i = 0; i < size; ++i)        
	 {            
		 struct TreeNode *temp = NULL;            
		 temp = queue[head++];            
		 res[*returnSize][i] = temp->val;             
		 if(temp->left)             
 		{                  
			 queue[tail++] = temp->left;            
		 }           
		 if(temp->right)              
		 {                 
			 queue[tail++] = temp->right;              
		 }   

		 (*returnSize)++;    
	 }    
	 return res;
 }