算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 二叉树的右视图，我们先来看题面：
https://leetcode-cn.com/problems/binary-tree-right-side-view/
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
题意
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例
解题
https://www.imooc.com/article/303711
思路一：广度优化搜索
当对二叉树进行层次遍历时，每一层最右边的节点是最后访问的。题目中要求返回从右侧所能看到的节点值，正是这里每层最右边的节点。那么保留每层最后的访问节点，就能得到需要求的答案。
这里使用队列存储。
具体可参照代码进行理解。
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root == None:
return []
# 导入 deque 创建队列
from collections import deque
queue = deque([root])
res = []
while queue:
size = len(queue)
# 这里用 size 记录二叉树每层的节点数，
for i in range(size):
# 弹出节点
node = queue.popleft()
# 先将左节点入队
if node.left != None:
queue.append(node.left)
# 再将右节点入队
if node.right != None:
queue.append(node.right)
# 队列先入先出，如果 i 等于 size - 1，
# 那么这里就是最右边的节点，这个就要得到的结果，将其放入返回列表中
if i == size - 1:
res.append(node.val)
return res 复制
思路二：深度优化搜索
同样的，这道题也能够使用深度优化搜索来解决。
在搜索的过程中，我们先访问右子树，再访问左子树。那么每层的第一个节点就是最右边节点。这个时候，只要知道二叉树的深度，则可以得到最终的答案。
具体可参照代码进行理解。
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
res = []
def _dfs(node, depth):
if node == None:
return []
# res 的索引表示二叉树的深度
# 若当前的深度的节点不存在于 res 中，
# 表示该层的最右边节点还未将其添加到 res 中
# 将其加入到节点中
if depth == len(res):
res.append(node.val)
# 往一下层访问，先访问右子树，在访问左子树
depth += 1
_dfs(node.right, depth)
_dfs(node.left, depth)
_dfs(root, 0)
return res 复制
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。