题解 | #从上往下打印二叉树##非递归层次遍历二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

typedef struct stQueue{
    int front;
    int rear;
    struct TreeNode *pstArray[1000];
}queue;

//进队列（指针进队）
void queuePush(queue *pstQueue, struct TreeNode* root)
{
    if ((NULL != root) && (pstQueue->front != (pstQueue->rear + 1) % 1000))
    {
        pstQueue->pstArray[pstQueue->rear++] = root;
    }
    return;
}

//出队列（出队仅需要值val）
int queueTop(queue *pstQueue)
{
    int iValue = 0;
    if (pstQueue->front != pstQueue->rear)
    {
        iValue = pstQueue->pstArray[pstQueue->front++]->val;
    }
    return iValue;
}

int* PrintFromTopToBottom(struct TreeNode* root, int* returnSize ) {
    // write code here
    int *piArray = NULL;
    int front = 0;
    int iLength = 0;
    struct TreeNode* pTemp = NULL;
    queue stQueue;
    if (NULL == root)
        return NULL;
    memset(&stQueue, 0, sizeof(stQueue));
    queuePush(&stQueue, root);	//根节点进队
    front = stQueue.front;	//从队列的第一个节点开始遍历
    while (front != stQueue.rear)	//直到遍历完所有的节点
    {
        pTemp = stQueue.pstArray[front];		//每遍历一个节点，让它的左右孩子节点分别入队
        queuePush(&stQueue, pTemp->left);
        queuePush(&stQueue, pTemp->right);
        front++;
    }
    iLength = stQueue.rear - stQueue.front;		//队列长，即树的长度
    piArray = (int *)malloc(sizeof(int) * iLength);
    
    for (front = 0; front < iLength; front++)	//遍历队列，出元素
    {
        piArray[front] = queueTop(&stQueue);
    }
    *returnSize = iLength;
    
    return piArray;
}