二叉树的右视图

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

例如，对于二叉树：

    1
   / \
  2   3
   \   \
    5   4

从右侧观察，能看到节点 1、3、4，因此返回 [1, 3, 4]。

解题过程

1. 问题分析
   题目要求的是每一层的最右节点。这提示我们需要按层遍历二叉树（即广度优先搜索，BFS），并在遍历每一层时记录最后一个节点。

2. 关键思路
   使用队列进行层序遍历。在每一层中，依次处理节点，并将该层最后一个节点的值加入结果列表。

3. 算法步骤

   • 如果根节点为空，直接返回空列表。
   • 初始化一个队列，将根节点加入队列。
   • 当队列不为空时：
     • 获取当前层的节点数量 level_size。
     • 遍历当前层的所有节点（循环 level_size 次）：
       • 弹出队首节点。
       • 如果该节点是当前层的最后一个节点（即循环到 level_size - 1 时），将其值加入结果列表。
       • 将当前节点的左子节点和右子节点（如果存在）加入队列。
   • 返回结果列表。

4. 示例演示
   以示例二叉树为例：

   • 初始队列: [1]，当前层大小为 1，最后一个节点是 1，结果列表为 [1]。
   • 下一层队列: [2, 3]，当前层大小为 2，遍历到第二个节点 3 时加入结果列表，变为 [1, 3]。
   • 下一层队列: [5, 4]，当前层大小为 2，最后一个节点是 4，结果列表变为 [1, 3, 4]。

5. 复杂度分析

   • 时间复杂度：O(N)，每个节点被处理一次。
   • 空间复杂度：O(N)，队列最多存储一层的节点数，最坏情况下为 O(N)。

6. 代码实现（Python）

from collections import deque

def rightSideView(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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

通过以上步骤，我们可以高效地得到二叉树的右视图。这个方法确保了每一层只保留最右侧的节点，且遍历顺序符合题目要求。