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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */

#include <stdlib.h>
int** Print(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    (*returnSize) = 0;
    if(root == NULL)    return NULL;
    int **level = (int **)malloc(sizeof(int *)*1000);
    *returnColumnSizes =  (int*)malloc(sizeof(int) * 1000);
    int k = 0;
    int head = 750, nhead;
    int tail = 750, ntail;
    struct TreeNode * queue[1500];
    queue[tail++] = root;
    while(head != tail){
        ntail = tail;
        nhead = head;
        k = 0;
        level[*returnSize] = (int *)malloc(sizeof(int)*(ntail - head));
        while((head < ntail)&&(tail > nhead)){
            if((*returnSize)%2 == 0){
                struct TreeNode *p = queue[head];
                level[*returnSize][k++] = p->val; 
                if(p->left)
                    queue[tail++] = p->left;
                if(p->right)
                    queue[tail++] = p->right;
                head++;
            }
            else if((*returnSize)%2 != 0){
                struct TreeNode *p = queue[--tail];
                level[*returnSize][k++] = p->val;
                if(p->right)
                    queue[--head] = p->right;
                if(p->left)
                    queue[--head] = p->left;
            }
        }
        (*returnColumnSizes)[(*returnSize)++] = k;
    }
    return level;
}