企业官网建设流程全解析

LeetCode 199. 二叉树的右视图

题目描述

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

示例：

输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 1 <--- / \ 2 3 <--- \ \ 5 4 <---

解法一：BFS 层序遍历（推荐）

层序遍历每一层，取每层的最后一个节点。

classSolution{publicList<Integer>rightSideView(TreeNoderoot){List<Integer>res=newArrayList<>();if(root==null)returnres;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){res.add(node.val);}if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}}returnres;}}

复杂度：

· 时间复杂度：O(n)，每个节点访问一次
· 空间复杂度：O(n)，队列最多存一层节点

解法二：DFS（先访问右子树）

按「根 → 右 → 左」的顺序 DFS，每个深度第一次访问到的节点即为该层最右节点。

classSolution{publicList<Integer>rightSideView(TreeNoderoot){List<Integer>res=newArrayList<>();dfs(root,0,res);returnres;}privatevoiddfs(TreeNodenode,intdepth,List<Integer>res){if(node==null)return;// 每个深度第一次到达，就是该层最右侧节点if(depth==res.size()){res.add(node.val);}dfs(node.right,depth+1,res);// 先右dfs(node.left,depth+1,res);// 后左}}

复杂度：

· 时间复杂度：O(n)
· 空间复杂度：O(h)，h 为树高（递归栈深度）

两种解法对比

解法 思路 优点 缺点
BFS 层序遍历取每层最后一个 直观易懂 需要额外队列空间
DFS 先右后左，记录首次到达的深度 空间复杂度更优（对平衡树而言） 略微抽象

关键点

1. BFS：判断 i == size - 1 就能拿到每层最右节点，注意 size 必须提前缓存，因为循环中队列长度会变化。
2. DFS：depth == res.size() 是核心判断——当递归到新的一层时，res 尚未添加该层元素，此时访问的节点就是该层最右节点（因为先走右子树）。
3. 空树直接返回空列表。

两种解法都建议掌握，面试中 BFS 更容易想到，DFS 则体现对递归顺序的理解。