题解 | #按之字形顺序打印二叉树#

C语言解题思路

1. 本质上还是层序遍历输出二叉树
2. 在层序遍历二叉树中，构建队列顺序存储每一层
3. 设置深度标识k，奇偶深度存储的方向相反。

重点来了！返回值一直没有搞懂，从代码中可以看要返回一个int **类型的指针，也就是按照每一层进行返回。需要使用malloc初始化一个最多1500层的int*类型的数组。接下来在每一层遍历的时候，需要根据该层的叶子个数继续初始化malloc int类型空间。这样就解决了返回值的问题。接下来是*returnSize,这个变量用于记录行数，也就是二叉树层数。最后就是int **returnColumnSizes参数，记录每一层的节点个数。和返回值类似，第一步初始化1500层。第二步记录每一层的个数。

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    if (pRoot == NULL)
		return NULL;
	int pre = 0, end = 0,k=1,tempend=0,a=1;
	int** nums=(int **)malloc(sizeof(int *)*1500);
	*returnColumnSizes = (int*)malloc(sizeof(int) * 1500);
	int tempnum = 0;
	struct TreeNode* Nodes[1000] ;
	Nodes[end++] = pRoot;
	//只要队列不为空
	nums[0] = (int*)malloc(sizeof(int));
	nums[0][0] = pRoot->val;
	*returnSize = 0;
	*returnColumnSizes[0] =1;
	while (Nodes[pre]) {
		k++;
		tempend = end;
		//一个循环一层
		for (; pre < tempend; pre++) {
			if (Nodes[pre]->left != NULL)
				Nodes[end++] = Nodes[pre]->left;
			if (Nodes[pre]->right != NULL)
				Nodes[end++] = Nodes[pre]->right;

		}
		tempnum= end - tempend;
		if (pre == end)
			break;
		//returnColumnSizes[k-1] = (int*)malloc(sizeof(int));
		(* returnColumnSizes)[k - 1] = tempnum;
		nums[k - 1] = (int*)malloc(sizeof(int) * tempnum);
		//偶数层，从右往左输出
		if (k % 2 == 0) {
			int j = 0;
			for (int i = end; i > tempend; i--) {
				nums[k - 1][j++]= Nodes[i - 1]->val;
			}
			(* returnColumnSizes)[k - 1] = j;
				
		}
		//奇数层，从左往右输出
		else {
			int j = 0;
			for (int i = tempend; i < end; i++)
				nums[k - 1][j++] = Nodes[i]->val;
			(* returnColumnSizes)[k - 1] = j;
		}
	}
	k--;
	*returnSize = k;
	return nums;
}