AlgoPressAppearance
0199-二叉树的右视图
https://leetcode.cn/problems/binary-tree-right-side-view
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1: 
输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2:
输入: [1,null,3] 输出: [1,3] 示例 3:
输入: [] 输出: []
提示:
二叉树的节点个数的范围是 [0,100] -100 <= Node.val <= 100
思路 BFS
- 如果二叉树右节点一直存在，则添加入 二叉树的右节点（因为右节点会挡住左节点）
- 如果二叉树右节点不存在，但是左节点存在，则添加入左节点 （因为右节点没有挡住左节点）
- 如果都不存在，循环结束
上述思路有问题：当为下图时， 需要输出 [1,3,4]， 而不是 1,3
1
/ \
2 3
/
4
那么就需要使用 BFS 展开，每一层输出最后一个数字
参考代码
csharp
public class Solution {
public IList<int> RightSideView(TreeNode root) {
List<int> result = new List<int>();
Queue<TreeNode> queue = new Queue<TreeNode>();
if(root != null){
queue.Enqueue(root);
while(queue.Count > 0){
int count = queue.Count;
int lastVal = 0;
for(int i=0; i<count; i++){
TreeNode node = queue.Dequeue();
lastVal = node.val;
if(node.left != null){
queue.Enqueue(node.left);
}
if(node.right != null){
queue.Enqueue(node.right);
}
}
result.Add(lastVal);
}
}
return result;
}
}
思路 DFS 【官方，很巧妙】
我们按照 根节点 -> 右子树 -> 左子树 深度优先遍历，这样每次优先访问到的总是右节点 我们访问的时候记录深度信息，那么在当前深度下，第一个访问到的节点就是能被看到的节点
参考代码
csharp
public class Solution {
List<int> result = new List<int>();
private void dfs(TreeNode node, int depth){
if(node == null){
return;
}
//每个深度记录第一个
if(result.Count == depth){
result.Add(node.val);
}
depth++;
dfs(node.right,depth);
dfs(node.left,depth);
}
public IList<int> RightSideView(TreeNode root) {
dfs(root,0);
return result;
}
}