LeetCode 199：二叉树的右视图 —— 利用层序遍历获取每层最右节点

给定一棵二叉树的根节点root想象自己站在二叉树的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例输入root [1,2,3,null,5,null,4]对应二叉树1 / \ 2 3 \ \ 5 4从右侧观察1 3 4输出[1,3,4]另一个例子输入root [1,null,3]结构1 \ 3输出[1,3]二、为什么这道题值得学习这道题是二叉树遍历中的经典问题也是面试高频题。它主要考察二叉树层序遍历BFS 广度优先搜索如何获取每一层指定位置的节点很多同学看到“右视图”可能会想到从右边一直遍历。但实际上二叉树右视图的本质是每一层中最右边的节点。例如1 / \ 2 3 / \ 4 5按照层序遍历第一层1第二层2 3第三层4 5右视图看到的就是1 3 5所以只需要找到每一层最后访问的节点即可。三、核心思想层序遍历 记录每层最后一个节点二叉树层序遍历也就是 BFS。遍历顺序从上到下 从左到右例如1 / \ 2 3 / \ 4 5访问顺序1 2 3 4 5如果我们知道当前层有多少个节点。那么这一层最后被访问的节点就是右视图看到的节点。所以算法步骤使用队列保存节点每次处理一层节点记录当前层最后一个节点加入结果数组四、解题思路分析1. 使用队列进行层序遍历首先定义队列QueueTreeNode用于保存当前需要访问的节点。初始化将根节点加入队列。2. 获取当前层节点数量每次进入循环记录当前层节点数量int size queue.size();例如当前队列[2,3]说明这一层有两个节点。3. 判断是否为当前层最后一个节点遍历当前层for(int i 0; i size; i)当i size - 1说明当前节点是这一层最后访问的节点。也就是右视图看到的节点。加入答案result.add(node.val);五、代码实现BFS层序遍历class Solution { public ListInteger rightSideView(TreeNode root) { ListInteger result new ArrayList(); if(root null){ return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); while(!queue.isEmpty()){ // 当前层节点数量 int size queue.size(); for(int i 0; i size; i){ TreeNode node 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); } } } return result; } }六、过程图解例如1 / \ 2 3 \ \ 5 4要求右视图第一层队列[1]数量size 1访问1因为i size - 1所以加入result [1]加入下一层[2,3]第二层队列[2,3]数量size 2访问节点2i 0不是最后一个。访问节点3i 1满足i size - 1加入result [1,3]第三层队列[5,4]访问节点5不是最后。访问节点4最后一个节点。加入result [1,3,4]最终答案[1,3,4]七、复杂度分析时间复杂度O(N)原因每个节点都会被访问一次。空间复杂度O(N)原因队列最多存储一层节点。在最坏情况下完全二叉树最后一层节点数量接近N/2所以空间复杂度为O(N)八、另一种方法DFS递归除了 BFS。也可以使用深度优先遍历。核心思想优先访问右子树。因为右边节点更可能出现在右视图中。遍历顺序根节点 ↓ 右子树 ↓ 左子树例如1 / \ 2 3 \ 4访问1 3 4 2每个深度第一次访问到的节点就是该层右侧节点。代码class Solution { ListInteger result new ArrayList(); public ListInteger rightSideView(TreeNode root) { dfs(root,0); return result; } private void dfs(TreeNode root,int depth){ if(root null){ return; } // 当前深度第一次访问 if(depth result.size()){ result.add(root.val); } // 优先遍历右子树 dfs(root.right,depth 1); // 再遍历左子树 dfs(root.left,depth 1); } }九、两种方法比较方法思路时间复杂度空间复杂度BFS每层记录最后节点O(N)O(N)DFS优先访问右节点O(N)O(H)面试中更加推荐✅ BFS层序遍历因为它更加符合“右视图”的定义。十、常见错误与避坑指南❌ 错误一只遍历右子树很多人认为右视图就是一直走右孩子。这是错误的。例如1 / 2 \ 3如果只走右边只能得到1但是实际右视图1 2 3原因右视图看的是每层最右节点。不是整棵树的右链。❌ 错误二记录每层第一个节点错误i 0这样得到的是左视图。右视图应该记录i size - 1❌ 错误三忽略空树情况如果root null应该返回[]所以需要提前判断if(root null)十一、面试高频追问1. 为什么 BFS 可以解决右视图因为BFS 按层遍历。而右视图要求每层最右节点。所以记录每层最后访问节点即可。2. 为什么 DFS 要先访问右子树因为右子树节点优先被访问。每个深度第一次出现的节点就是该层最右节点。3. 如果要求左视图怎么办只需要改变遍历顺序左视图记录每层第一个节点。DFS优先访问左子树。总结LeetCode 199 的核心思想是二叉树右视图 每一层最右侧节点。通过层序遍历 BFS控制每层节点数量遍历当前层 ↓ 记录最后一个节点 ↓ 加入答案这道题不仅考察二叉树遍历还帮助理解BFS在树结构中的应用如何处理二叉树层级信息每层节点的统计技巧