102 二叉树的层序遍历

# 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

广度优先:

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

# 鼓励我一下：

觉得还不错的话，给我的项目点个star吧

# 点个Star支持我一下~

← 199 二叉树的右视图 200 题岛屿数量 →