LeetCode 199. 二叉树的右视图题目描述给定一个二叉树的根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 1 --- / \ 2 3 --- \ \ 5 4 ---解法一BFS 层序遍历推荐层序遍历每一层取每层的最后一个节点。classSolution{publicListIntegerrightSideView(TreeNoderoot){ListIntegerresnewArrayList();if(rootnull)returnres;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();// 当前层的最后一个节点就是右视图看到的节点if(isize-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{publicListIntegerrightSideView(TreeNoderoot){ListIntegerresnewArrayList();dfs(root,0,res);returnres;}privatevoiddfs(TreeNodenode,intdepth,ListIntegerres){if(nodenull)return;// 每个深度第一次到达就是该层最右侧节点if(depthres.size()){res.add(node.val);}dfs(node.right,depth1,res);// 先右dfs(node.left,depth1,res);// 后左}}复杂度· 时间复杂度O(n)· 空间复杂度O(h)h 为树高递归栈深度两种解法对比解法 思路 优点 缺点BFS 层序遍历取每层最后一个 直观易懂 需要额外队列空间DFS 先右后左记录首次到达的深度 空间复杂度更优对平衡树而言 略微抽象关键点BFS判断 i size - 1 就能拿到每层最右节点注意 size 必须提前缓存因为循环中队列长度会变化。DFSdepth res.size() 是核心判断——当递归到新的一层时res 尚未添加该层元素此时访问的节点就是该层最右节点因为先走右子树。空树直接返回空列表。两种解法都建议掌握面试中 BFS 更容易想到DFS 则体现对递归顺序的理解。