# 102 二叉树的层序遍历
# 题目链接
# 难度：中等
# 思路分析：
深度优先和广度优先
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
深度优先:
/**
* @param {TreeNode} root
* @return {number[][]}
*/
// dfs深度优先
var levelOrder = function(root) {
const res = [];
const levelNum = 0; // 当前层级
dfs(root, levelNum);
function dfs(node, step) {
if (node) {
// 当前节点是否有值
if (res[step]) {
// 该层级已添加过节点 在当前层级中继续添加
res[step].push(node.val);
} else {
// 当前层级未添加过节点 创建一个数组 添加节点
res.push([node.val]);
}
// 循环下个节点 增加层级
dfs(node.left, step + 1);
dfs(node.right, step + 1);
}
}
return res;
};
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
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
广度优先:
var levelOrder = function(root) {
const ret = [];
if (!root) return ret;
const q = []; // 栈
q.push(root);
while (q.length !== 0) {
const currentLevelSize = q.length; // 记录下一层级的数量
ret.push([]); // 层级初始化
// 遍历广度 同一层级的元素都取出来
for (let i = 1; i <= currentLevelSize; ++i) {
const node = q.shift(); // 取出同一层级的元素
ret[ret.length - 1].push(node.val); // 添加广度同一节点
// 下个层级
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return ret;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧