二叉树的右视图

题目描述：给定一棵二叉树的根节点，要求返回从右侧观察这棵树时能看到的节点值，顺序从顶部到底部。换句话说，返回每一层最右边的节点值。

解题思路：这个问题本质上是二叉树的层序遍历的变种。在标准的层序遍历中，我们会按层访问每个节点。要获得右视图，我们只需要在遍历每一层时，记录该层的最后一个节点（即最右侧节点）的值。这可以通过广度优先搜索（BFS）或深度优先搜索（DFS）两种策略实现。

方法一：广度优先搜索（BFS）- 使用队列

BFS是解决这个问题最直观的方法。我们使用一个队列来辅助进行层序遍历。

1. 初始化：如果根节点为空，直接返回空列表。否则，将根节点放入队列。
2. 循环处理每一层：只要队列不为空，就说明还有层未处理。
   a. 记录当前层的节点数量：在开始处理当前层之前，先获取当前队列的长度 levelSize。这个长度就是当前层的节点个数。
   b. 遍历当前层的所有节点：用一个循环，从队列中弹出 levelSize 个节点。
   - 对于弹出的每个节点，先检查其左右子节点，如果不为空，则按顺序（先左后右）加入队列，为下一层的遍历做准备。
   - 关键点：当我们遍历到当前层的最后一个节点（即循环变量 i 等于 levelSize - 1 时），这个节点就是从右边能看到节点。我们将这个节点的值加入到结果列表中。
3. 返回结果：当队列为空，所有层都处理完毕后，返回结果列表。

图解过程（以二叉树 [1,2,3,null,5,null,4] 为例）：

    1        <-- 第0层
   / \
  2   3      <-- 第1层
   \   \
    5   4    <-- 第2层

• 初始化：队列 = [1]，结果列表 = []
• 处理第0层：levelSize = 1
  • 弹出节点 1。i=0 是最后一个节点，将值 1 加入结果。将其左右子节点 2 和 3 入队。
  • 结果列表 = [1]，队列 = [2, 3]
• 处理第1层：levelSize = 2
  • 弹出节点 2 (i=0)。它不是最后一个节点，不记录。将其右子节点 5 入队。
  • 队列 = [3, 5]
  • 弹出节点 3 (i=1，是最后一个节点)。将值 3 加入结果。将其右子节点 4 入队。
  • 结果列表 = [1, 3]，队列 = [5, 4]
• 处理第2层：levelSize = 2
  • 弹出节点 5 (i=0，是最后一个节点？不，这一层有两个节点)。它不是最后一个节点，不记录。它没有子节点。
  • 队列 = [4]
  • 弹出节点 4 (i=1，是最后一个节点)。将值 4 加入结果。它没有子节点。
  • 结果列表 = [1, 3, 4]，队列 = []
• 队列为空，返回结果 [1, 3, 4]。

代码实现（Python）：

from collections import deque
# 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: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            # 遍历当前层的所有节点
            for i in range(level_size):
                node = queue.popleft()
                # 如果是当前层的最后一个节点，则加入结果
                if i == level_size - 1:
                    result.append(node.val)
                # 将左右子节点加入队列，为下一层做准备
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
        return result

方法二：深度优先搜索（DFS）- 递归

DFS方法采用了一种不同的思路：我们按照 根节点 -> 右子树 -> 左子树 的顺序进行遍历（这确保了每一层我们总是先访问到最右边的节点），同时记录当前节点的深度。

1. 递归函数设计：定义一个递归函数 dfs(node, depth)。
   • node：当前正在访问的节点。
   • depth：当前节点所在的深度（根节点深度为0）。
2. 递归过程：
   • 如果当前节点为空，直接返回。
   • 关键判断：如果当前深度 depth 等于结果列表 result 的长度，说明我们是第一次到达这个深度。由于我们是先递归右子树，这个“第一次到达”的节点必然是该深度下最右边的节点。因此，将当前节点的值加入结果列表。
   • 然后，先递归调用右子节点（depth + 1），再递归调用左子节点（depth + 1）。
3. 启动递归：从根节点和深度0开始递归。

图解过程（同样以 [1,2,3,null,5,null,4] 为例）：

• 调用 dfs(1, 0)：
  • depth=0, result 长度=0，相等。将 1 加入结果。result = [1]
  • 先递归右子树：dfs(3, 1)
    • depth=1, result 长度=1，相等。将 3 加入结果。result = [1, 3]
    • 先递归右子树：dfs(4, 2)
      • depth=2, result 长度=2，相等。将 4 加入结果。result = [1, 3, 4]
      • 递归左子树（为空，返回）
    • 再递归左子树（为空，返回）
  • 再递归左子树：dfs(2, 1)
    • depth=1, result 长度=2，不相等（说明深度1已经有节点3了），不加入结果。
    • 先递归右子树：dfs(5, 2)
      • depth=2, result 长度=3，不相等（说明深度2已经有节点4了），不加入结果。
    • 再递归左子树（为空，返回）
• 返回结果 [1, 3, 4]。

代码实现（Python）：

# 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: Optional[TreeNode]) -> List[int]:
        result = []
        
        def dfs(node, depth):
            if not node:
                return
            # 如果当前深度等于结果列表长度，说明是第一次访问该深度，当前节点即为最右节点
            if depth == len(result):
                result.append(node.val)
            # 先右后左，保证每层先访问到最右边的节点
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        dfs(root, 0)
        return result

总结：

• BFS方法：逻辑清晰，易于理解。通过队列进行层序遍历，记录每层的最后一个节点。
• DFS方法：代码简洁，利用递归顺序（先右后左）和深度信息，巧妙地确保每层第一个被访问到的节点就是最右节点。
• 两种方法的时间复杂度和空间复杂度都是 O(N)，其中 N 为树中的节点数目。在实际面试中，掌握其中一种即可，如果能阐述两种方法的思路则更佳。