# 层序遍历二叉树
leetcode：102：二叉树的层序遍历题链
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
TreeNode
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
1
2
3
4
5
6
7
2
3
4
5
6
7
# 借助队列迭代
var levelOrder = function (root) {
if (!root) {
return []
}
let res = []
let queue = [root]
while (queue.length > 0) {
// 当前层的节点个数
let nowSize = queue.length
let nowLevelRes = []
while (nowSize > 0) {
// 取出第一个元素
let p = queue.shift()
nowLevelRes.push(p.val)
if (p.left) {
queue.push(p.left)
}
if (p.right) {
queue.push(p.right)
}
nowSize--
}
// 放入当前层的结果
res.push(nowLevelRes)
}
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
27
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
# DFS递归
var levelOrder = function (root) {
if (!root) {
return []
}
let res = []
const dfs = (deep, node, res) => {
// 如果结果的深度小于当前深度,放入空数组
if (res.length < deep) {
res.push([])
}
res[deep - 1].push(node.val)
if (node.left) dfs(deep + 1, node.left, res)
if (node.right) dfs(deep + 1, node.right, res)
}
dfs(1, root, res)
return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17