LeetCode 199. 二叉树的右视图

当对二叉树进行层次遍历时，每一层最右边的节点是最后访问的。题目中要求返回从右侧所能看到的节点值，正是这里每层最右边的节点。那么保留每层最后的访问节点，就能得到需要求的答案。

这里使用队列存储。

具体可参照代码进行理解。

同样的，这道题也能够使用深度优化搜索来解决。

在搜索的过程中，我们先访问右子树，再访问左子树。那么每层的第一个节点就是最右边节点。这个时候，只要知道二叉树的深度，则可以得到最终的答案。

具体可参照代码进行理解。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#  self.val = x
#  self.left = None
#  self.right = None

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#  self.val = x
#  self.left = None
#  self.right = None

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