讨论/题目交流/请教一道二叉树的层次遍历/
请教一道二叉树的层次遍历
#define MAX_LEN 1000
typedef struct TreeNode TreeNode;

typedef struct {
    int front;
    int rear;
    int size;
    TreeNode *arr[MAX_LEN];
} Queue;

Queue *createQueue()
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    if (queue == NULL) {
        return NULL;
    }

    queue->front = -1;
    queue->rear = -1;
    queue->size = 0;
    memset(queue->arr, 0x0, sizeof(TreeNode *) * MAX_LEN);
    return queue;
}

void queuePush(Queue *queue, TreeNode *node)
{
    if ((queue == NULL) || (queue->rear >= MAX_LEN)) {
        return;
    }

    queue->rear++;
    queue->size++;
    queue->arr[queue->rear] = node;
    return;
}

TreeNode *queuePop(Queue *queue)
{
    if ((queue == NULL) || (queue->size == 0)) {
        return NULL;
    }

    queue->front++;
    queue->size--;
    return queue->arr[queue->front];
}

int isEmpty(Queue *queue)
{
    if ((queue == NULL) || (queue->size == 0)) {
        return 1;
    }

    return 0;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
    if (root == NULL) {
        return NULL;
    }

    int i;
    int levelTmp;
    int index = 0;
    int level;
    int **ans = (int **)malloc(sizeof(int *) * MAX_LEN);
    int *colSize = (int *)malloc(sizeof(int) * MAX_LEN);
    TreeNode *tmp = NULL;
    Queue *queue = createQueue();

    queuePush(queue, root);
    level = 1;
    colSize[index] = level;

    while(isEmpty(queue) != 1) {
        i = 0;
        levelTmp = 0;
        while ((index % 2 == 0) && (level != 0)) {
            tmp = queuePop(queue);
            level--;
            ans[index] = (int *)malloc(sizeof(int) * MAX_LEN);
            memset(ans[index], 0x0, sizeof(int) * MAX_LEN);
            // printf("index0 :i %d  tmp  %d\n", i, tmp->val);
            ans[index][i] = tmp->val;
            i++;

            if (tmp->left != NULL) {
                queuePush(queue, tmp->left);
                levelTmp++;
            }

            if (tmp->right != NULL) {
                queuePush(queue, tmp->right);
                levelTmp++;
            }
        }

        while ((index % 2 != 0) && (level != 0)) {
            tmp = queuePop(queue);
            level--;
            ans[index] = (int *)malloc(sizeof(int) * MAX_LEN);
            memset(ans[index], 0x0, sizeof(int) * MAX_LEN);
            //printf("index1 :i %d  tmp  %d\n", i, tmp->val);
            ans[index][i] = tmp->val;
            i++;

            if (tmp->right != NULL) {
                queuePush(queue, tmp->right);
                levelTmp++;
            }

            if (tmp->left != NULL) {
                queuePush(queue, tmp->left);
                levelTmp++;
            }
        }

        index++;
        level = levelTmp;
        printf("index %d  level %d\n", index, level);
        colSize[index] = level;
    }

    *returnSize = index;
    *returnColumnSizes = colSize;
    return ans;
}

为什么输出每个数组的第一个数没有被赋值
image.png

展开讨论
freedom发起于 2020-03-19
最近编辑于 2020-03-20
共 1 个讨论

跟你的 i 有关吧,中间只有一次 i = 0; 但是两次 while 循环里都用了 i

另外没看懂两次 while 循环是什么思路。

层序的套路一般是:

  1. root 节点 push 到队列里
  2. while (!que.isEmpty()) 判断队列不为空的大循环
    21. 得到队列当前的大小 int len = que.size()
    22. 一个 for (int i = 0; i < len; i++) ,用来确定这一层的节点有多少个
    23. 将节点从队列里取出 que.pop() ,记录输出,然后把左右子节点 push 到队列里
    24. 当 len 个节点操作完成,说明这一层的节点已经遍历完毕,退出 for 循环
    25. 回到上一层 while 循环,进行下一层节点的遍历,层数加一
  3. 当队列为空时,说明全部遍历完毕,返回结果

代码

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
    if (root == NULL) return NULL;

    int i;
    int index = 0;
    int **ans = (int **)malloc(sizeof(int *) * MAX_LEN);
    int *colSize = (int *)malloc(sizeof(int) * MAX_LEN);
    
    TreeNode *tmp = NULL;
    Queue *queue = createQueue();
    queuePush(queue, root);

    while(isEmpty(queue) != 1)
    {
        colSize[index] = queue->size;
        ans[index] = (int *)malloc(sizeof(int) * colSize[index]);
        memset(ans[index], 0x0, sizeof(int) * colSize[index]);  // 循环里每次都申请和清空,应该写在外面
        for (i = 0; i < colSize[index]; i++)
        {
            tmp = queuePop(queue);

            ans[index][i] = tmp->val;
            printf("index = %d, i = %d, ans[index][i] = %d\n", index, i, ans[index][i]);
            
            if (tmp->left != NULL) 
            {
                queuePush(queue, tmp->left);
            }

            if (tmp->right != NULL)
            {
                queuePush(queue, tmp->right);
            }
        }
        index++;
    }

    *returnSize = index;
    *returnColumnSizes = colSize;
    return ans;
}