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

#include <stdbool.h>
typedef struct TreeNode Node;
typedef struct TreeNode* pNode;
void ReverseNum(int *num, int numlen);

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    if(pRoot == NULL) return NULL;
    //一颗正常的树需要：
    //创建一个二维数组
    *returnSize = 0;
    int **ret = (int **)malloc(sizeof(int *) * 1500); //申请行空间，最多1500行
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1500);  
    //创建一个队列
    pNode queue[1500];
    int front = 0;
    int rear = 0;
    //定义一个flag
    bool flag = true;
    //头节点入队
    queue[rear++] = pRoot;
    //上一层出栈，下一层进栈
    while(front != rear){
        int prerear = rear;//记录上一层进栈的尾指针
        int i = 0;//记录出栈节点数
        ret[*returnSize] = (int *)malloc(sizeof(int) * (prerear - front));//申请列空间,最多上一行的两倍
        while(front < prerear){ //front指向头节点，当头结点指向本层数据时候做以下操作
		  	//上一层出栈
            pNode p = queue[front++];
            ret[*returnSize][i++] = p->val; //数组存值
		  	//下一层入栈
            if(p->left != NULL) queue[rear++] = p->left;
            if(p->right != NULL) queue[rear++] = p->right;
        }
        (*returnColumnSizes)[*returnSize] = i; 
		//当flag==false时候翻转这一数组
        if(flag == false) ReverseNum(ret[*returnSize], i);
        (*returnSize)++;
	  	//翻转flag
        flag = !flag;
    }
    return ret;
}

//简单的翻转数组
void ReverseNum(int *num, int numlen){
    for(int i = 0; i < numlen / 2; i++){
        int tmp = num[numlen - i -1];
        num[numlen - i -1] = num[i];
        num[i] = tmp;
    }
}