题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

样例

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]

算法1 BFS O(n)

一层一层来

1. 将根节点插入队列中
2. 创建一个新队列，用来顺序保存下一层所有子节点
3. 对于当前队列中的所有节点，按顺序依次将儿子加入新的队列，并将当前节点值记录在答案中；
4. 重复步骤2-3，直到队列为空

时间复杂度

树中每个节点仅会进队出队一次，所有时间复杂度为O(n)。

C 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#define MAX_RETURN_NUM 1000
int** levelOrder(struct TreeNode* root, int *returnSize, int** returnColumnSizes) {
    // malloc(sizeof(int*) * MAX_RETURN_NUM) 不初始化为0
    int **ret = (int**)malloc(sizeof(int*) * MAX_RETURN_NUM); 
    *returnColumnSizes = (int*)calloc(MAX_RETURN_NUM, sizeof(int));

    *returnSize = 0; // 数组总长度

    struct TreeNode *queue[10000];
    int outIndex = 0;
    int inIndex = 0;
    if (root == NULL) {return NULL;}
    queue[inIndex ++] = root;
    int levelcount = inIndex - outIndex;
    int count = 0;
    while (levelcount > 0) {
        count ++ ;
        ret[*returnSize] = (int*)calloc(levelcount, sizeof(int));
        (*returnColumnSizes)[*returnSize] = levelcount; // 每一行的长度
        // 没一层的动作
        for (int i = 0; i < levelcount; i ++ ) {
            if (queue[outIndex]->left != NULL) {
                queue[inIndex ++ ] = queue[outIndex]->left;
            }
            if (queue[outIndex]->right != NULL) {
                queue[inIndex ++ ] = queue[outIndex]->right;
            }
            ret[*returnSize][i] = queue[outIndex]->val;
            outIndex ++ ;
        }
        (*returnSize) ++ ;
        levelcount = inIndex - outIndex;
    }
    return ret;
}