# 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
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧