0102. 二叉树的层序遍历【中等】
1. 📝 题目描述
给你二叉树的根节点 root,返回其节点值的 层序遍历。 (即逐层地,从左到右访问所有节点)。
示例 1:

txt
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]1
2
2
示例 2:
txt
输入:root = [1]
输出:[[1]]1
2
2
示例 3:
txt
输入:root = []
输出:[]1
2
2
提示:
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
2. 🎯 s.1 - BFS(队列)
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().
*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (!root) {
*returnColumnSizes = NULL;
return NULL;
}
int** ans = (int**)malloc(2000 * sizeof(int*));
*returnColumnSizes = (int*)malloc(2000 * sizeof(int));
struct TreeNode* queue[2001];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
int size = rear - front;
ans[*returnSize] = (int*)malloc(size * sizeof(int));
(*returnColumnSizes)[*returnSize] = size;
for (int i = 0; i < size; i++) {
struct TreeNode* node = queue[front++];
ans[*returnSize][i] = node->val;
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
(*returnSize)++;
}
return ans;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (!root) return []
const ans = []
const queue = [root]
while (queue.length) {
const size = queue.length
const level = []
for (let i = 0; i < size; i++) {
const node = queue.shift()
level.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
ans.push(level)
}
return ans
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(level)
return ans1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
- 时间复杂度:
,其中 是二叉树的节点数,每个节点恰好入队、出队各一次 - 空间复杂度:
,队列最多同时存储一层的节点,最坏情况为完全二叉树的最后一层约 个节点
算法思路:
- 用队列实现 BFS,初始将根节点入队
- 每轮循环先记录当前队列长度
size(即当前层的节点数),依次出队size个节点,将它们的值收集到level数组中,同时将非空子节点入队 - 每轮结束后将
level加入结果,直到队列为空