199. 二叉树的右视图#

生活中的算法#

想象你站在摩天大楼的右侧，想要记录每层楼最右边的窗户位置。当楼层从下往上排列时，每个楼层你只能看到最右侧的窗户。这个场景完美对应了今天要解决的算法问题——二叉树的右视图。

就像城市规划师需要确定天际线的轮廓一样，我们需要找到二叉树每一层最右侧的节点值。

问题描述#

题目目标#

给定一棵二叉树的根节点 root，返回从右侧观察这棵树时，按从上到下顺序能看到的节点值。

示例 1#

输入： root = [1,2,3,null,5,null,4] 输出： [1,3,4] 二叉树示意：

text

说明： 每一层从右侧看到的节点依次是第 1 层的 1、第 2 层的 3、第 3 层的 4，所以结果为 [1,3,4]。

补充说明#

题目关注的是“每层最右边能看到的节点”。
可以用层序遍历取每层最后一个节点，也可以用优先访问右子树的 DFS。

最直观的解法：层序遍历法#

就像用无人机逐层扫描大楼，我们可以使用广度优先搜索（BFS）逐层遍历二叉树，记录每层的最后一个节点。

算法步骤#

使用队列进行层序遍历
记录每层节点数量
将每层最后一个节点加入结果列表

示例运行过程：

层序遍历顺序：
第一层：1 → 最后一个节点是1
第二层：2→3 → 最后一个节点是3
第三层：5→4 → 最后一个节点是4
最终结果：[1,3,4]

plaintext

Java实现：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 存放右视图结果：每层只保留最右侧节点值
        List<Integer> result = new ArrayList<>();
        // 边界处理：空树没有右视图
        if (root == null) return result;

        // 队列用于层序遍历（BFS）
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);

        // 按层处理所有节点
        while (!queue.isEmpty()) {
            // 当前层节点总数
            int levelSize = queue.size();
            // 遍历当前层每个节点
            for (int i = 0; i < levelSize; i++) {
                // 出队一个当前层节点
                TreeNode node = queue.poll();
                // 当前层最后一个被处理的节点，就是右视图可见节点
                if (i == levelSize - 1) result.add(node.val);

                // 左孩子存在则入队，留给下一层
                if (node.left != null) queue.offer(node.left);
                // 右孩子存在则入队，留给下一层
                if (node.right != null) queue.offer(node.right);
            }
        }
        // 返回从上到下的右视图列表
        return result;
    }
}

java

优化解法：深度优先遍历法#

如果大楼有快速通道可以直达顶层，何必逐层扫描？我们可以通过深度优先遍历（DFS）优先访问右子树，在首次到达新深度时记录节点值。

递归实现原理#

维护一个记录当前最大深度的变量
优先遍历右子树
当首次到达新深度时记录节点值

示例运行过程（示例树）：

递归路径：1→3→4（深度0→1→2）
然后回溯到3→1→2→5（深度1→0→1→2）
但深度2已被记录，不再更新
最终结果：[1,3,4]

plaintext

Java代码：

class Solution {
    // 全局结果列表：result[depth] 存储该深度首次访问到的节点（即右侧节点）
    List<Integer> result = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        // 从根节点开始 DFS，根深度记为 0
        dfs(root, 0);
        // 返回右视图结果
        return result;
    }

    private void dfs(TreeNode node, int depth) {
        // 递归终止条件：空节点直接返回
        if (node == null) return;

        // 若是首次到达该深度，说明当前节点是这一层“最先看到的”节点
        // 因为我们先访问右子树，所以首次节点就是右视图节点
        if (depth == result.size()) {
            result.add(node.val);
        }

        // 先访问右子树，确保右侧节点优先被记录
        dfs(node.right, depth + 1);
        // 再访问左子树，补充未覆盖到的层
        dfs(node.left, depth + 1);
    }
}

java

两种解法对比#

方法	时间复杂度	空间复杂度	特点
层序遍历（BFS）	O(n)	O(n)	直观易懂，适合层相关操作
深度优先（DFS）	O(n)	O(h)	空间更优（h为树高）

题目模式总结#

这道题揭示了树遍历类问题的两个核心思路：

层序维度处理：使用BFS逐层扫描，适合需要处理层级信息的场景
深度优先优化：通过遍历顺序控制（先右后左）和深度记录实现高效访问

小结#

通过这道题，我们掌握了两种观察二叉树的新视角：物理上的右侧视图，算法上的层序与深度优先双解法。就像城市规划师需要多角度观察建筑，优秀的算法工程师也应该掌握多种解题视角。

记住：BFS像用广角镜头捕捉层级全景，DFS像用长焦镜头深入探索细节。根据问题特点选择合适的”镜头”，才能拍出最优美的算法画卷。