二叉树的右视图

题目描述
给定一棵二叉树的根节点 root，想象你站在树的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。例如：

    1
   / \
  2   3
   \   \
    5   4

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

解题思路
这个问题本质上是要求二叉树每一层最右边的节点。我们可以通过层序遍历（BFS）或深度优先遍历（DFS）来解决。

方法一：BFS（层序遍历）

1. 使用队列进行层序遍历，每次处理一层。
2. 遍历每一层时，记录该层最后一个节点的值。
3. 因为每层最后一个节点就是从右侧能看到的节点。

步骤详解

1. 如果根节点为空，直接返回空列表。
2. 初始化队列，将根节点加入队列。
3. 循环处理队列直到为空：
   • 当前层的节点数 = 队列当前大小。
   • 遍历当前层所有节点（循环节点数次）：
     • 弹出队首节点。
     • 如果是当前层最后一个节点（即当前循环的最后一个节点），将其值加入结果列表。
     • 将该节点的左子节点和右子节点（如果存在）加入队列。
4. 返回结果列表。

示例代码（Python）

from collections import deque

def rightSideView(root):
    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（深度优先遍历）

1. 按照“根节点 → 右子树 → 左子树”的顺序遍历。
2. 记录当前深度，如果当前深度首次出现，则该节点是右侧视图的节点（因为先访问右子树）。

步骤详解

1. 初始化结果列表和最大深度记录（可以用字典或变量）。
2. 递归遍历二叉树：
   • 如果当前深度尚未记录节点值，将当前节点值加入结果列表。
   • 先递归处理右子树，再处理左子树（确保每层先访问最右侧节点）。
3. 返回结果列表。

示例代码（Python）

def rightSideView(root):
    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

复杂度分析

• 时间复杂度：O(N)，每个节点被访问一次。
• 空间复杂度：O(N)，队列或递归栈的空间消耗。

关键点

• BFS 按层处理时，每层最后一个节点即为右视图节点。
• DFS 通过控制遍历顺序（先右后左）和深度记录，确保每层第一个访问的节点是最右侧节点。