大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定二叉树根节点，按照从顶到底的顺序，返回右侧能看到的节点值。”
2、题目描述
给定一个二叉树的 根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1： 输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2： 输入: [1,null,3] 输出: [1,3]
二、解题
1、思路分析
这道题的思路还是很明确的。
首先就是层序遍历这棵树，然后取层序遍历结果的每一项的最后一个值就是右侧能看到的节点值。
二叉树的层序遍历可以使用广度优先搜索BFS实现。
执行广度优先搜索算法，对每一层从左向右访问，保存每一项最后访问的节点，在遍历完整棵树得到每一项最右节点值，如图所示：
红色节点自上而下组成答案。
2、代码实现
代码参考：
class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (i == size - 1) { //将当前层的最后一个节点放入结果列表 res.add(node.val); } } } return res; } }
3、时间复杂度
时间复杂度：O(n)
深度优先搜索最多访问每个节点一次，是线性复杂度。
空间复杂度：O(n)
最坏情况下，栈内会包含接近树高度的节点数量，也就是O(n)的空间。
三、总结
从左向右开始进行BFS层序遍历。
保存每一层的最后一个节点值。
