难度: Medium
给定一个二叉树的 根节点 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 注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/
运行时间: 23 ms
内存: 16.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
# 方法1：层序遍历，取每层最右边的值即可
# 方法2：右视图需要先遍历右子树，如果节点满足条件则存下来，
# 什么节点是满足条件的呢？由于每层只有一个节点可以保留，
# 所以只有当前深度比答案list长度要长时，才会保留当前元素
# 当然，我们优先遍历右子树，可以保证是右视图。
result = []
self.dfs(root, result, 0)
return result
def dfs(self, root, result, depth):
if not root:
return
if len(result) == depth:
result.append(root.val)
self.dfs(root.right, result, depth+1)
self.dfs(root.left, result, depth+1)
这个题解采用了深度优先搜索（DFS）的方式来遍历二叉树。首先定义一个辅助函数dfs，该函数接受当前节点root、结果列表result和当前深度depth作为参数。在dfs函数中，如果当前节点为空，则直接返回。如果当前深度等于结果列表的长度，说明这是该层第一个被访问的节点，因此将其值添加到结果列表中。然后先递归地对右子节点进行dfs，再对左子节点进行dfs。这样可以保证每层最右边的节点先被访问到。最终，返回结果列表。
时间复杂度: O(n)
空间复杂度: O(h)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
result = [] # 结果列表
self.dfs(root, result, 0) # 从根节点开始深度优先搜索
return result
def dfs(self, root, result, depth):
if not root: # 如果当前节点为空，返回
return
if len(result) == depth: # 如果当前深度等于结果列表的长度，将节点值添加到结果列表
result.append(root.val)
self.dfs(root.right, result, depth+1) # 先遍历右子树
self.dfs(root.left, result, depth+1) # 再遍历左子树
在计算二叉树的右视图时，目的是要捕捉每一层最右侧的节点。如果我们先遍历右子树，那么每一层最右侧的节点将是第一个被访问到的，并且它们会首先被添加到结果列表中。这种顺序确保了我们总是能够正确地记录下每一层的最右侧节点，从而生成正确的右视图。如果我们先遍历左子树，那么在右子树有节点的情况下，左子树的节点可能会被错误地视为某层的最右侧节点。
在DFS过程中，我们使用一个整数`depth`来表示当前节点的深度（从0开始）。结果列表`result`的长度表示已经记录的层数。当我们在某个深度`depth`处遇到一个节点，如果此时`result`的长度也是`depth`，这意味着在这个深度我们还没有添加任何节点到结果列表中。因为我们是按照从右到左的顺序遍历节点，所以该层第一个被访问到的节点自然是该层最右侧的节点，将其添加到结果列表确保了正确记录每层的最右侧节点。
在这个题解中，节点的具体数值（无论是负数、零还是正数）并不影响算法的逻辑。算法的目标是识别并记录每一层最右侧的节点，而节点的值仅仅被添加到结果列表中用于表示这些节点。因此，节点值的具体数值不会影响结果列表中的值选择；只是这些值直接反映了每层最右侧节点的实际值。