199. 二叉树的右视图

中等

给定一个二叉树的 根节点 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]

解释：

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

📝 核心笔记：二叉树的右视图 (Binary Tree Right Side View)

1. 核心思想 (一句话总结)

“先右后左，抢占先机：每一层我只收录第一个见到的节点。”

• 普通前序遍历：根 -> 左 -> 右。
• 变形前序遍历：根 -> 右 -> 左。
• 效果：在这种遍历顺序下，对于每一层来说，最右边的节点一定是最先被访问到的。
• 我们利用 ans 列表的长度作为“当前已记录的最大深度”的标记。

2. 算法流程 (DFS 递归)

1. 递归参数：当前节点 root，当前深度 depth。
2. 判断收录：

• • 检查 depth == ans.size()。
  • ans.size() 代表目前我们已经收集了多少层的右视图。
  • 如果 depth 等于它，说明我们第一次来到了这一层（且是从右边来的），赶紧把当前节点加入 ans。
  • 如果 depth < ans.size()，说明这一层之前已经有（更右边的）节点被访问并加入过了，当前节点被挡住了，跳过。

1. 递归顺序 (关键)：

• • 先 dfs(right)：优先去右边探路。
  • 后 dfs(left)：右边没了再补左边。

🔍 代码回忆清单

// 题目：LC 199. Binary Tree Right Side View
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    private void dfs(TreeNode root, int depth, List<Integer> ans) {
        if (root == null) {
            return;
        }
        
        // 核心逻辑：
        // ans.size() 其实就是"当前已记录的最大层数"
        // 当我们来到一个新的深度 depth，如果它等于 size，说明这是该层第一个被访问的节点
        // 因为我们是"先右后左"，所以这个节点一定是该层最右边的
        if (depth == ans.size()) { 
            ans.add(root.val);
        }
        
        // 顺序极其重要：先右后左
        dfs(root.right, depth + 1, ans); 
        dfs(root.left, depth + 1, ans);
    }
}

⚡ 快速复习 CheckList (对比 BFS)

• [ ] BFS 怎么做？(面试常问)

• • 使用队列进行层序遍历（LC 102）。
  • 每一层循环结束时，把当前层的最后一个节点加入结果集。
  • BFS 的空间复杂度是 $O(W)$ (最大宽度)，DFS 是 $O(H)$ (高度)。在树很宽但很浅时，DFS 略省空间；在树很深时，BFS 省空间。

• [ ] 如果把 dfs 里左右顺序换一下会怎样？

• • 如果变成 根 -> 左 -> 右，那记录的就是 二叉树的左视图 了。

• [ ] 逻辑陷阱

• • 有些人会误以为右视图就是“一直往右走 (node.right)”。
  • 错。如果右子树断了，我们在右侧能看到左子树的节点。DFS 能够完美处理这种情况（当右递归回来后，继续走左递归，此时 depth 变深，ans.size() 还没跟上，左子树的节点就会被补录进去）。

🖼️ 数字演练

树结构：

       1
     /   \
    2     3
     \     
      5

(注意：2 的右孩子是 5，3 没有孩子)

1. dfs(1, 0):

• • 0 == size(0). Add 1. ans=[1].
  • Call dfs(3, 1) (Right child).

1. dfs(3, 1):

• • 1 == size(1). Add 3. ans=[1, 3].
  • 3 has no kids. Return.

1. Back to 1, Call dfs(2, 1) (Left child).
2. dfs(2, 1):

• • 1 != size(2). (Depth 1 已经被 3 占了). Skip add.
  • Call dfs(5, 2) (Right child of 2).

1. dfs(5, 2):

• • 2 == size(2). Add 5. ans=[1, 3, 5].
  • Return.

Result: [1, 3, 5]. (正确，因为 3 挡不住 5)