二叉树的右视图

题目描述
给定一棵二叉树的根节点 root，要求返回从右侧观察这棵树时能看到的节点值，即每一层最右边的节点。例如：

    1
   / \
  2   3
   \   \
    5   4

右视图为 [1, 3, 4]。

解题思路
右视图的本质是二叉树的每一层最后一个节点（按从左到右的层序遍历顺序）。因此可以通过层序遍历（BFS）或DFS（优先访问右子树）解决。

方法一：BFS（层序遍历）

1. 核心思想：使用队列进行层序遍历，每次记录当前层的最后一个节点值。

2. 步骤：

   • 若根节点为空，直接返回空列表。
   • 初始化队列，将根节点加入队列。
   • 循环遍历每一层：
     • 获取当前层的节点数量 size。
     • 遍历当前层所有节点，依次出队并将其左右子节点入队。
     • 当前层最后一个节点（即第 size 个节点）即为右视图节点，加入结果列表。
   • 返回结果列表。

3. 示例代码（Python）：

from collections import deque

def rightSideView(root):
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i == size - 1:  # 当前层最后一个节点
                res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return res

方法二：DFS（递归）

1. 核心思想：按照「根节点 → 右子树 → 左子树」的顺序访问，确保每层最先访问到的是最右侧节点。

2. 步骤：

   • 初始化结果列表 res 和当前深度 depth=0。
   • 递归遍历时，若当前深度等于 res 的长度（表示该层尚未记录节点），说明当前节点是该层第一个被访问的节点（即最右侧节点），加入结果列表。
   • 递归时先访问右子节点，再访问左子节点，深度增加 1。

3. 示例代码（Python）：

def rightSideView(root):
    res = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(res):  # 当前深度尚未记录节点
            res.append(node.val)
        dfs(node.right, depth + 1)  # 先右后左
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return res

复杂度分析

• 时间复杂度：O(N)，每个节点被访问一次。
• 空间复杂度：O(N)，BFS 的队列或 DFS 的递归栈最坏情况下为 O(N)。

总结

• BFS 直观符合层序逻辑，DFS 通过调整访问顺序优化空间（最坏情况相同）。
• 关键点：右视图 = 每层最后一个节点。