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

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

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    // write code here
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1500);

    if (pRoot == NULL)
    {
        *returnSize = 0;
        (*returnColumnSizes)[0] = 0;
        return NULL;
    }
    //创建二维数组
    int** ret = (int**)malloc(sizeof(int*) * 1500);
    for (int i = 0; i < 1500; i++)
    {
        ret[i] = (int*)malloc(sizeof(int) * 800);
    }
    int i = 0;//行
    int j = 0;//列
    //循环队列
    struct TreeNode* team[1000]; 
    struct TreeNode* head = pRoot;
    int front = 0;
    int tail = 0;
    team[0] = pRoot;
    tail++;
    int col = 0;
    //栈
    struct TreeNode* shed[1000]; 
    int s = 0;

    struct TreeNode* p = NULL;
    struct TreeNode* tmp = NULL;
    while((front != tail) || s != 0)
    {
        if (front == tail)
        {
            for (--s; s >= 0; s--)
            {
                team[tail++] = shed[s];
                tail = tail % 1000;
            }
            (*returnColumnSizes)[i] = j;
            s = 0;
            i++;
            j = 0;
            col++;
        }

        //出队
        p = team[front++];
        front = front % 1000;


        ret[i][j++] = p->val;
        //入栈
        if (col % 2 == 0)
        {
            if (p->left != NULL)
            {
                shed[s++] = p->left;
            }
            if (p->right != NULL)
            {
                shed[s++] = p->right;
            }
        }
        else
        {
            if (p->right != NULL)
            {
                shed[s++] = p->right;
            }
            if (p->left != NULL)
            {
                shed[s++] = p->left;
            }
            
        }
    }
    (*returnColumnSizes)[i] = j;
    *returnSize = ++i;
    return ret;
}