LC199　二叉树的右视图¶

中等通过率 73.8%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索广度优先搜索二叉树

一句话

逐层扫描，每层最右边的那个节点就是从右侧看到的。

解题思路¶

这题考什么¶

站在树的右侧往左看，每一层只能看到最靠右的那一个节点 —— 它前面的同层节点全被它挡住了。所以答案就是「逐层取最后一个节点的值」，长度等于树的深度。

容易踩的直觉陷阱：右视图不等于「一路沿 right 指针走下去」。某一层最右的节点未必是谁的右孩子 —— 当右子树在这一层根本没有节点时，看到的就是左子树里的节点。题面示例 2 的 [1,2,3,4,null,null,null,5] 正是如此：第四层只有 5，它挂在 4 的左边，而 4 又挂在 2 的左边；只顺着 right 走会在 3 处断掉，输出 [1,3]，比正确答案 [1,3,4,5] 少两项。

实现沿用层序遍历（广度优先搜索，BFS）的整层替换写法：手里握着当前层的全部节点（从左到右），取最后一个记进答案，再用它们的孩子拼出下一层。层序模板见树的基础与遍历的「二叉树的三种遍历」一节。

数据规模与复杂度¶

节点数在 [0, 100]，节点值在 [-100, 100]。每个节点入列表一次、被展开一次，时间 O(n)；空间是最宽一层的节点数，量级 O(n)。规模很小，怎么写都够；选 BFS 是因为「每层最右」这个条件直接对应层的概念，不必额外记深度。

坑在哪¶

不能只沿 right 指针下探，理由见上，示例 2 就是专门用来打掉这个写法的。
拼下一层必须先左后右，层内顺序才是从左到右，取 level[-1] 才真的是最右。写反了取到的是最左边那个节点。
空树返回 []。题面示例 4 给的正是空树；不先判空，第一轮就会对 None 取 .left。
答案的顺序是从顶到底，与层的推进顺序一致，逐层追加即可，不需要任何排序或反转。

参考实现¶

solutions/leetcode/LC199/sol.py
from typing import List, Optional


class Solution:
    def rightSideView(self, root: "Optional[TreeNode]") -> List[int]:
        out: List[int] = []
        # 空树看不到任何节点；这一句也保证 level 里不会混进 None
        if root is None:
            return out
        # 循环不变量：level 是当前层的全部节点，且已按从左到右排好
        level = [root]
        while level:
            # 从右侧看，本层只有最后一个节点没被挡住
            out.append(level[-1].val)
            # 用本层的孩子拼下一层；先左后右保证下一层仍是从左到右，
            # 这正是上一行取 [-1] 能拿到「最右」的前提
            nxt: List["TreeNode"] = []
            for node in level:
                if node.left is not None:
                    nxt.append(node.left)
                if node.right is not None:
                    nxt.append(node.right)
            level = nxt
        # 层的推进顺序就是从顶到底，答案天然有序
        return out

LC199 二叉树的右视图¶