199. 二叉树的右视图

题目链接：199. 二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

核心思考：层序遍历（BFS）

想要看到二叉树的“右视图”，本质上就是获取每一层中最右侧的那个节点。

1. 层序遍历：通过层序遍历（BFS），我们可以逐层访问二叉树。使用队列 deque 来维护当前层的节点。
2. 提取层级最右节点：在逐层处理时，对于每一层，队列中最后入队的元素（即当前层的最后一个元素）就是由于我们从左向右压入节点，而位于最右侧的节点。
3. 流程：
   • 记录当前队列的长度（即当前层的节点总数）。
   • 将队列末尾的元素加入结果集 ans。
   • 依次弹出当前层的所有节点，并将其左右子节点（如果存在）按序压入队列中，供下一层遍历。

这种方法能够保证我们按从上到下的顺序，精准捕捉每一层“最右侧”的视野。

解题思路 (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]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        while q:
            # 队列中的最后一个元素即为当前层最右侧的节点
            ans.append(q[-1].val)
            # 遍历并处理当前层的所有节点
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点都会且仅会进入队列并被处理一次。
• 空间复杂度：$O(N)$，在最坏情况下（例如完全二叉树），队列中最多会同时存在层级规模的节点（约为 $N/2$）。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
                return []
            ans = []
            q = deque([root])
            while q:
                # 队列中的最后一个元素即为当前层最右侧的节点
                ans.append(q[-1].val)
                # 遍历并处理当前层的所有节点
                for _ in range(len(q)):
                    node = q.popleft()
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
            return ans

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.rightSideView(root)
    print(result)

if __name__ == "__main__":
    main()