TikTok 二叉树右视图：每层最右节点与稀疏边界

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练题名为右视图；相关描述的数字编号与题名不一致，按题名成文，编号细节不据此推断。
• 节点有 value/left/right，树无环；按深度由浅到深输出。

解题路线

1. DFS 先访问右，再访问左。某深度第一次到达的节点就是从右侧看的最右节点，之后同深度跳过。
2. 使用栈时左孩子先压、右后压，保证弹出顺序右优先。深度==结果长度时追加。
3. 右视图不等于一直沿 right 指针走；右分支较浅时，左侧更深节点仍可见。
4. BFS 的每层最后节点可作为独立验证方法；构造空树、左右缺失与深度不齐，检验身份和输出层数。

手动走一遍

根1、右3无孩子、左2有右5，结果[1,3,5]。只有左链时仍能看见每层一个节点，不能返回只含根。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def right_view(root):
    """Node has value/left/right; assumes an acyclic tree."""
    result = []
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if node is None:
            continue
        if depth == len(result):
            result.append(node.value)
        stack.append((node.left, depth + 1))
        stack.append((node.right, depth + 1))
    return result

复杂度

O(n) 时间，DFS O(h) 工作空间和 O(h) 输出；最坏退化 O(n)。BFS 使用 O(w)。

易错点与追问

容易失分的边界

• 仅走右链。
• 栈入栈方向颠倒变左视图。
• 根据不一致编号改写题目。

继续深挖

• 如何求左视图？
• 如果输入是数组层序，空位如何建树？