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

int find(struct TreeNode* pRoot)
{
    if (!pRoot) return 0;
    int left = find(pRoot->left);
    int right = find(pRoot->right);
    return (left > right ? left : right) + 1;
}
int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) {
    if (!pRoot) {
	return NULL;
	*returnSize=0;
	}
    int front = 0, rear = 0;
    *returnSize = find(pRoot);
    int** arr = malloc((*returnSize) * (sizeof(int*)));
    (*returnColumnSizes) = malloc(sizeof(int) * (*returnSize));
    struct TreeNode* queue[1500];
    queue[rear++] = pRoot;
    for (int row = 0; row < *returnSize; row++)
    {
        int cst = rear;
        (*returnColumnSizes)[row] = rear - front;
        arr[row] = malloc((*returnColumnSizes)[row] * sizeof(int));
        if (row % 2 == 0) {
            for (int col = 1; col <= (*returnColumnSizes)[row]; col++)
            {
                struct TreeNode* node = queue[cst - col];
                arr[row][col - 1] = queue[front++]->val;
                if (node->right) queue[rear++] = node->right;
                if (node->left) queue[rear++] = node->left;
            }
        }
        else {
            for (int col = 1; col <= (*returnColumnSizes)[row]; col++)
            {
                struct TreeNode* node = queue[cst - col];
                arr[row][col - 1] = queue[front++]->val;
                if (node->left) queue[rear++] = node->left;
                if (node->right) queue[rear++] = node->right;
            }
        }
    }
    return arr;
}