102. 二叉树的层序遍历

[hey-monster]

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

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]
 

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：广度搜索 + 队列

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(root == NULL){
        *returnSize = 0;
        *returnColumnSizes = 0;
        return NULL;
    }
    int** ret = (int**)malloc(sizeof(int*) * 2000);
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);

    struct TreeNode* queue[2001];
    int left = 0;
    int right = 0;
    queue[right++] = root;
    while(left < right){
        int size = right - left;
        int* current = (int*)malloc(sizeof(int) * size);
        for(int i = 0; i < size; ++i){
            current[i] = queue[left]->val;
            if(queue[left]->left != NULL){
                queue[right++] = queue[left]->left;
            }
            if(queue[left]->right != NULL){
                queue[right++] = queue[left]->right;
            }
            left++;
        }
        ret[(*returnSize)] = current;
        (*returnColumnSizes)[(*returnSize)++] = size;
    }
    return ret;
}