二叉树的右视图-LeetCode

二叉树的右视图

🎯 问题描述

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

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

**示例 2

输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]

💻 解题思路

思路：DFS 深度优先搜索（右优先遍历）

核心思想：利用 DFS 优先遍历右子树。对于每一层深度，第一个被访问到的节点，一定是最靠右的节点。

代码实现

from typing import Optional, List

# 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]:
        ans = []
        def dfs(node, depth):
            if not node:
                return
            # 核心逻辑：当当前深度等于结果数组长度时，说明是第一次到达该层
            # 因为我们是“右优先”遍历，所以第一个到达该层的节点一定是最右边的
            if depth == len(ans):
                ans.append(node.val)
            # 优先遍历右子树，再遍历左子树
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        dfs(root, 0)
        return ans

📊 性能分析

• 时间复杂度：$O(n)$。其中 $n$ 是二叉树的节点数量，每个节点都会被访问一次。
• 空间复杂度：$O(h)$。取决于递归调用栈的深度，即二叉树的高度 $h$。

💡 思考

这道题用 DFS 解法的精髓在于遍历顺序。

• 如果题目改为求“左视图”，只需要将 dfs(node.right) 和 dfs(node.left) 的顺序互换即可。
• 判断条件 depth == len(ans) 是一个非常经典的技巧，它利用结果集的大小来隐式地判断“当前层是否已经被记录过”，避免了使用额外的哈希表或数组来记录层级状态。