企业官网建设流程全解析

【LeetCode热题100】Java详解：二叉树的右视图（含BFS/DFS双解法与工程实践）

面向人群

• 正在准备技术面试（尤其是大厂后端、算法岗）的开发者
• 已掌握基础二叉树操作，希望深入理解层序遍历与空间优化技巧的学习者
• 刷 LeetCode「热题100」或「二叉树专题」的中级程序员
• 对 BFS/DFS 应用场景与性能权衡感兴趣的工程人员

📌 本文适合已能手写二叉树前中后序遍历的读者。若对队列、栈等辅助数据结构不熟悉，建议先完成 LeetCode 第102题（二叉树的层序遍历）。

关键词

LeetCode 199、二叉树的右视图、BFS、DFS、层序遍历、深度优先搜索、广度优先搜索、队列、栈、树的层级、右视图、面试高频题、空间优化、时间复杂度分析

阅读前必须掌握的基础

在深入阅读本文前，请确保你已熟练掌握以下知识点：

1. 二叉树的基本结构

   • TreeNode定义（val,left,right）
   • 树的深度（depth）与高度（height）概念

2. 两种核心遍历思想

   • 深度优先搜索（DFS）：使用递归或栈，沿一条路径走到尽头再回溯
   • 广度优先搜索（BFS）：使用队列，按层从左到右访问节点

3. Java 常用集合类

   • Queue<TreeNode>（通常用LinkedList实现）
   • Deque<TreeNode>（双端队列，可用于模拟栈）
   • HashMap<Integer, Integer>的基本操作

4. 层序遍历（Level Order Traversal）

   • 能实现标准层序遍历（返回List<List<Integer>>）
   • 理解“每层最后一个节点”的含义

5. 时间与空间复杂度基础

   • 能分析 O(n)、O(log n)、O(h) 等常见复杂度
   • 理解最坏情况（如链状树）对空间的影响

✅ 推荐前置练习：

• LeetCode 102：二叉树的层序遍历
• LeetCode 104：二叉树的最大深度
• LeetCode 107：二叉树的层序遍历 II

一、原题回顾

题目链接：199. 二叉树的右视图

题目描述

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

示例 1：

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

可视化解释：

1 <—— 右视图看到 1 / \ 2 3 <—— 右视图看到 3（2被3挡住） \ \ 5 4 <—— 右视图看到 4（5被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

二、原题分析

2.1 什么是“右视图”？

“右视图”并非字面意义上的“所有右孩子”，而是指：从右侧垂直观察时，每一层中最后被看到的节点。

关键洞察：

• 同一层中，最右边的节点会挡住其左侧所有节点
• 因此，右视图 =每层的最后一个节点（从左到右顺序）

✅ 举例：若某层节点为[A, B, C, D]，则右视图看到的是D

2.2 为什么不能只取“右子树”？

反例：

1 / 2 \ 3

• 右子树为空，但右视图应为[1,2,3]
• 因为第2层只有2，第3层只有3，它们都是各自层的“最右”

因此，必须按层处理，而非简单遍历右分支。

三、答案构思：两种主流解法

本题的核心在于获取每层的最后一个节点。有两种经典思路：

💡 两种方法时间复杂度均为 O(n)，但空间使用和实现细节有差异。

四、完整答案与代码实现（Java）

方法一：深度优先搜索（DFS）—— 先右后左

思路

• 使用 DFS 遍历树，优先访问右子树
• 维护一个Map<depth, value>，记录每个深度第一次访问到的节点值
• 由于先访问右子树，第一次访问某深度时，该节点必为该层最右

✅ 优势：可提前终止（若只需前 K 层），但本题需全部层

Java 代码（迭代版）

classSolution{publicList<Integer>rightSideView(TreeNoderoot){if(root==null)returnnewArrayList<>();Map<Integer,Integer>rightmostValueAtDepth=newHashMap<>();intmaxDepth=-1;Deque<TreeNode>nodeStack=newLinkedList<>();Deque<Integer>depthStack=newLinkedList<>();nodeStack.push(root);depthStack.push(0);while(!nodeStack.isEmpty()){TreeNodenode=nodeStack.pop();intdepth=depthStack.pop();if(node!=null){// 更新最大深度maxDepth=Math.max(maxDepth,depth);// 只记录每个深度第一次出现的节点（即最右）if(!rightmostValueAtDepth.containsKey(depth)){rightmostValueAtDepth.put(depth,node.val);}// 注意：先压入左子树，再压入右子树！// 因为栈是 LIFO，后压入的先弹出nodeStack.push(node.left);nodeStack.push(node.right);depthStack.push(depth+1);depthStack.push(depth+1);}}// 按深度顺序构建结果List<Integer>result=newArrayList<>();for(intdepth=0;depth<=maxDepth;depth++){result.add(rightmostValueAtDepth.get(depth));}returnresult;}}

递归版（更简洁）

classSolution{publicList<Integer>rightSideView(TreeNoderoot){List<Integer>result=newArrayList<>();dfs(root,0,result);returnresult;}privatevoiddfs(TreeNodenode,intdepth,List<Integer>result){if(node==null)return;// 如果当前深度等于结果列表大小，说明这是该层第一个访问的节点if(depth==result.size()){result.add(node.val);}// 先递归右子树！dfs(node.right,depth+1,result);dfs(node.left,depth+1,result);}}

✨ 递归版巧妙之处：利用result.size()作为“已处理的最大深度”，无需额外 Map

方法二：广度优先搜索（BFS）—— 层序遍历

思路

• 使用队列进行标准层序遍历
• 对每一层，不断更新该层的“最右值”
• 遍历完一层后，最后一次更新的值即为该层右视图节点

✅ 优势：逻辑直观，符合“按层处理”的直觉

Java 代码

classSolution{publicList<Integer>rightSideView(TreeNoderoot){if(root==null)returnnewArrayList<>();Map<Integer,Integer>rightmostValueAtDepth=newHashMap<>();intmaxDepth=-1;Queue<TreeNode>nodeQueue=newLinkedList<>();Queue<Integer>depthQueue=newLinkedList<>();nodeQueue.offer(root);depthQueue.offer(0);while(!nodeQueue.isEmpty()){TreeNodenode=nodeQueue.poll();intdepth=depthQueue.poll();if(node!=null){maxDepth=Math.max(maxDepth,depth);// 不断覆盖，最后一轮即为最右节点rightmostValueAtDepth.put(depth,node.val);// 先加左，再加右（保证层内从左到右）nodeQueue.offer(node.left);nodeQueue.offer(node.right);depthQueue.offer(depth+1);depthQueue.offer(depth+1);}}List<Integer>result=newArrayList<>();for(intdepth=0;depth<=maxDepth;depth++){result.add(rightmostValueAtDepth.get(depth));}returnresult;}}

优化版（无需 Map，直接取每层最后一个）

classSolution{publicList<Integer>rightSideView(TreeNoderoot){List<Integer>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();// 遍历当前层所有节点for(inti=0;i<size;i++){TreeNodenode=queue.poll();// 如果是该层最后一个节点，加入结果if(i==size-1){result.add(node.val);}if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}}returnresult;}}

✨ 此版本空间更优，无需存储深度信息，直接利用size控制层边界

五、代码分析与对比

• h= 树高，w= 最大层宽
• 平衡树：h = log n, w = n/2；链状树：h = n, w = 1
• BFS 优化版是面试中最推荐的写法

六、时间复杂度与空间复杂度深度分析

时间复杂度：O(n)

• 无论 DFS 还是 BFS，每个节点恰好被访问一次
• 构建结果列表需 O(h) 或 O(levels)，而 h ≤ n，故总时间 O(n)

空间复杂度

DFS（递归）

• 递归栈深度= 树高h
• 最好情况（平衡树）：O(log n)
• 最坏情况（链状树）：O(n)

BFS（优化版）

• 队列最大长度= 最宽层的节点数w
• 最好情况（链状树）：O(1)
• 最坏情况（完全二叉树最后一层）：O(n/2) = O(n)

💡 虽然最坏空间都是 O(n)，但实际内存占用不同：

• DFS 在深而窄的树上更省空间
• BFS 在宽而浅的树上更省空间

七、常见问题解答（FAQ）

Q1：为什么 DFS 要先访问右子树？

A：因为我们要确保每层第一次访问的节点是最右边的。若先访问左子树，则左节点会先被记录，导致错误。

Q2：BFS 中为什么可以不用 Map？

A：因为我们按层处理，每层循环结束时，最后一个节点就是最右节点，可直接加入结果，无需存储中间状态。

Q3：能否用前序/中序遍历解决？

A：不能。这些遍历无法自然按“层”组织节点，难以判断“是否为该层最后一个”。

Q4：如果要左视图怎么办？

A：两种方式：

• DFS：改为先访问左子树
• BFS：取每层第一个节点（i == 0）

Q5：如何同时获取左右视图？

A：BFS 中同时记录i == 0和i == size - 1的节点即可。

八、优化思路总结

8.1 空间优化

• 避免使用 Map：BFS 优化版直接利用层循环
• 避免存储深度：通过queue.size()控制层边界

8.2 代码简洁性优化

• 递归 DFS：利用result.size()代替深度计数
• 早期返回：空树直接返回空列表

8.3 扩展性优化

• 若需支持“任意角度视图”（如第 K 个可见节点），可返回每层完整列表
• 若树极大，可考虑迭代替代递归，防止栈溢出

九、数据结构与算法基础知识点回顾

9.1 树的遍历方式对比

9.2 队列 vs 栈

9.3 复杂度分析要点

• 时间：看节点访问次数
• 空间：
  • DFS：看递归深度或栈大小
  • BFS：看队列最大长度（即最大层宽）

十、面试官提问环节（模拟）

Q：BFS 优化版中，为什么queue.size()能代表当前层节点数？

A：因为在进入while循环时，队列中恰好包含当前层的所有节点。我们用size = queue.size()冻结该数量，然后通过for (int i=0; i<size; i++)精确处理这一层，同时将下一层节点加入队列，不影响当前层计数。

Q：如果要求返回“右视图的节点深度”，怎么办？

A：可在 BFS 中记录深度，或 DFS 中传递深度参数。例如递归 DFS：

if(depth==result.size()){result.add(node.val);depths.add(depth);// 同时记录深度}

Q：如何验证你的解法正确？

A：设计边界测试用例：

• 空树 →[]
• 单节点 →[val]
• 完全左偏树 → 所有节点都可见
• 完全右偏树 → 所有节点都可见
• 深层左子树遮挡 → 如示例2

十一、实际开发中的应用场景

11.1 UI 渲染与布局

• 在树形控件（如文件浏览器、组织架构图）中，右视图可表示最深层级的末级节点
• 用于计算滚动区域高度或展开默认路径

11.2 网络拓扑可视化

• 在网络设备层级图中，右视图可能代表边缘设备或终端节点
• 辅助监控系统快速定位末端节点状态

11.3 编译器 AST（抽象语法树）

• 右视图可能对应表达式中最右侧的操作数或变量
• 用于静态分析或代码高亮

11.4 游戏开发（技能树、科技树）

• 右视图可表示玩家当前解锁的最先进技能或科技
• 用于成就系统或进度展示

十二、相关题目推荐

🔗 建议按此顺序刷题，形成“层序遍历”知识体系。

十三、总结与延伸

13.1 核心思想提炼

• 右视图 = 每层最后一个节点
• BFS 天然按层处理，是最直观解法
• DFS 通过控制访问顺序（先右后左）也能实现
• 空间优化的关键是避免冗余存储

13.2 延伸思考

• 多叉树的右视图：同样适用 BFS，每层取最后一个子节点
• N 叉树：LeetCode 429 题，解法完全一致
• 带权右视图：若节点有权重，可能需要自定义“可见”规则
• 动态右视图：若树动态变化，可结合增量更新策略

13.3 面试答题建议

不要一上来就写代码！

1. 先澄清题意：“右视图是指每层最右边的节点，对吗？”
2. 举小例子验证理解（如示例1）
3. 提出两种思路（BFS/DFS），分析优劣
4. 选择一种实现（推荐 BFS 优化版）
5. 讨论边界情况和复杂度

掌握一道题，吃透一类题。
右视图的本质是“层序遍历的变种”，理解这一点，就能举一反三！