前端积累

# 199 二叉树的右视图

# 题目链接

# 难度：中等

# 思路分析：

深度优先、广度优先

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 代码：

深度优先:

var rightSideView = function(root) {
	if (!root) return []
	let res = [] // 结果
	let start = 0 // 树的深度 从0开始
	dfs(root, start, res)
	return res
}
function dfs(root, step, res) {
	if (root) {
		if (step === res.length) {
			res.push(root.val) // 数组长度等于树的深度时 添加当前值 因为右侧先遍历 有右侧先添加右侧
		}
		dfs(root.right, step + 1, res)
		dfs(root.left, step + 1, res)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

广度优先:

var rightSideView = function(root) {
	if (!root) return []
	let queue = [root] // 队列 把树顶加入队列
	let arr = [] // 用来存储每层最后个元素值
	while (queue.length > 0) {
		let len = queue.length // 当前层的广度
		while (len) {
			let node = queue.shift() // 依次取出当前层队列的元素 从左到右
			if (len === 1) arr.push(node.val) // 当是 当前一层的最后一个元素时，把值加入arr
			if (node.left) queue.push(node.left) // 先添加左侧的
			if (node.right) queue.push(node.right) // 最后添加右侧的 等到最后一个元素时即可添加右侧的值
			len--
		}
	}
	return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 鼓励我一下：

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

# 点个Star支持我一下~

← 102 二叉树的层序遍历 →