二叉树的层序遍历

题目

题目来源: LeetCode

实现

//先实现队列....

//获取树的最大深度
int TreeLevel(struct TreeNode* root){
	if (root == NULL){
		return 0;
	}
	int left = 0;
	int right = 0;
	return (left = TreeLevel(root->left)) > (right = TreeLevel(root->right)) ?
		left + 1 : right + 1;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
	Queue q;
	QueueInit(&q);
	//获取树的深度
	*returnSize = TreeLevel(root);
	//开辟矩阵
	int** martrix = (int**)malloc(sizeof(int*)* (*returnSize));
	//存放每一层数据个数的数组
	*returnColumnSizes = (int*)malloc(sizeof(int)* (*returnSize));
	if (root){
		QueuePush(&q, root);
	}
	int level = 0;
	while (QueueEmp(&q) == 1){
		int levelSize = QueueSize(&q);
		int i;
		//为矩阵每一行开辟空间
		martrix[level] = (int*)malloc(sizeof(int)* levelSize);
		//存放每一层数据的个数
		(*returnColumnSizes)[level] = levelSize;
		//循环放入矩阵中
		for (i = 0; i < levelSize; i++){
			struct TreeNode* root = QueueFront(&q);
			QueuePop(&q);
			martrix[level][i] = root->val;
			//左子树存在push左子树
			if (root->left){
				QueuePush(&q, root->left);
			}
			//右子树存在push右子树
			if (root->right){
				QueuePush(&q, root->right);
			}
		}
		++level;
		//每访问一层, 下一层的数据已经push进队列
	}
	return martrix;
}