【忍者算法】从城市天际线到二叉树右视图：如何捕捉每层最右的风景｜LeetCode 199 二叉树的右视图网站首页 技术交流

【忍者算法】从城市天际线到二叉树右视图：如何捕捉每层最右的风景｜LeetCode 199 二叉树的右视图

忍者算法_ 2025-06-08 12:01:03

简介【忍者算法】从城市天际线到二叉树右视图：如何捕捉每层最右的风景｜LeetCode 199 二叉树的右视图

从城市天际线到二叉树右视图：如何捕捉每层最右的风景

生活中的算法

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

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

问题描述

LeetCode第199题"二叉树的右视图"要求：给定一棵二叉树的根节点，返回从右侧观察这棵树时能看到的节点值列表。

例如，给定二叉树：

右侧视图结果为：[1, 3, 4]

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

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

算法步骤

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

示例运行过程：

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

Java实现：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        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;
    }
}

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

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

递归实现原理

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

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

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

Java代码：

class Solution {
    List<Integer> result = new ArrayList<>();
    
    public List<Integer> rightSideView(TreeNode root) {
        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);
    }
}