本题采用广度优先搜索层序遍历算法又称“层级末端节点捕获法”解决二叉树右视图的节点提取问题。其核心本质是利用双端队列对二叉树进行逐层水平扫描通过识别每一层遍历序列的终点物理位置来锁定视线可达节点。当前提供的源码实现了在时间复杂度 O(n) 和额外空间复杂度 O(w)其中 w 为二叉树的最大宽度条件下的精确层级过滤最终走向是按从上到下的顺序完整返回所有右侧可见节点的数值集合。一、 问题本质与数据模型对于给定的二叉树其“右视图”的物理定义为从树的右侧水平直视时能看到的节点集合。该场景包含以下核心物理规律与约束层级遮蔽物理特性在同一层相同深度的多个节点中位置靠右的节点会完全物理遮蔽位置靠左的节点。因此对于任意独立层级从右侧看去有且仅有一个节点可见。末端节点定位模型在标准的自左向右层序遍历BFS序列中当某层包含 n 个节点时下标为 n - 1 的节点即当前层的最后一个节点天然处于该层的最右端。为了准确捕获每一层的最右侧边界算法引入了“双端队列分层模型”。通过在进入每层循环前利用q.size()锁死当前层的节点总数建立严格的层级边界控制网确保在多层节点交替入队的过程中能够精准剥离并记录各个层级的末端元素。二、 算法演进对比在提取二叉树右视图节点的场景中基于队列的层序遍历法在边界锁定的直观性和稳定性上具备极限特征解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷深度优先搜索DFS右分支优先递归O(n)O(h)优先遍历右子树并记录当前深度当深度首次超过结果集大小时记录节点依赖全局计数器与递归深度栈在深度倾斜的拓扑下栈开销大显式全层序遍历后置过滤O(n)O(n)提取出二叉树的所有层级节点列表再对结果集执行遍历提取每层末尾产生了多余的中间二维结构内存空间二次分配造成算力损耗队列层序遍历即时捕获当前解法O(n)O(w)逐层推进并在出队时通过索引比对即时截获末端元素无多余分配满二叉树状态下底层队列需要同时容纳约 n/2 个节点消耗局部内存三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于while (!q.isEmpty())构建的全局层级循环与内部for循环的边界索引控制器其内部决策分支证明如下1. 层级规模锁定int n q.size();执行在遍历当前层之前截取当前队列内的元素数量。数学证明由于在处理上一层节点时已将其所有合法的直接子节点依序推入队列此时队列中存在的元素在拓扑层级上具有完全的同质性。将当前大小赋值给常量 n 能够完全物理隔离当前层与即将入队的下一层节点。2. 末端节点捕获分支if (i n - 1)执行将当前弹出节点的数值存入结果集ans.add(node.val);。数学证明因为for循环的计数器 i 从 0 严格步进到 n - 1且队列元素的移出顺序是自左向右。当 i 达到 n - 1 时代表当前弹出的节点是当前物理层级中的绝对最右侧节点判定为可见节点。3. 左子节点拓扑扩展if (node.left ! null)执行q.add(node.left);将左孩子推入队列。物理意义为下一层的横向扫描储备左侧基础数据维持自左向右的遍历时序不变。4. 右子节点拓扑扩展if (node.right ! null)执行q.add(node.right);将右孩子推入队列。物理意义右孩子在左孩子之后入队确保其在下一层循环中处于更靠近右侧的物理位置维持末端节点特征的延续。四、 算法执行状态机步进示例以输入二叉树root [1, 2, 3, null, 5, null, 4]为例规模 n 5最大宽度 w 2双端队列与结果集的状态机演进过程如下表所示步骤当前处理层级锁定规模 n遍历索引 i 与出队节点值触发的物理动作与结果变更队列内存状态空间说明初始---初始化根节点入队队列状态: [1]结果集: []1层级 01i 0 (节点 1)满足 i n - 1结果集追加 1压入左右子节点队列状态: [2, 3]结果集: [1]2层级 12i 0 (节点 2)不满足末端条件压入非空右子节点 5队列状态: [3, 5]结果集: [1]3层级 12i 1 (节点 3)满足 i n - 1结果集追加 3压入非空右子节点 4队列状态: [5, 4]结果集: [1, 3]4层级 22i 0 (节点 5)不满足末端条件左右子节点均为空无入队动作队列状态: [4]结果集: [1, 3]5层级 22i 1 (节点 4)满足 i n - 1结果集追加 4无入队动作队列状态: []结果集: [1, 3, 4]五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListInteger rightSideView(TreeNode root) { // 边界安全检查若根节点为空直接返回空列表 if (root null) { return List.of(); } ListInteger ans new ArrayList(); // 声明双端队列用于承载层序遍历的节点物理流 DequeTreeNode q new ArrayDeque(); q.add(root); // 全局控制网当队列不为空时持续按层向下推进 while (!q.isEmpty()) { // 锁定当前层级的节点总数建立层级隔离屏障 int n q.size(); // 线性扫描当前层级的所有节点 for (int i 0; i n; i) { TreeNode node q.poll(); // 核心判定当索引步进到当前层级的最后一个元素时截获该节点值 if (i n - 1) { ans.add(node.val); } // 拓扑扩展依据自左向右的时序优先推入左子节点 if (node.left ! null) { q.add(node.left); } // 拓扑扩展随后推入右子节点确保其处于下一层队列的末尾 if (node.right ! null) { q.add(node.right); } } } return ans; } }六、 复杂度分析1. 时间复杂度O(n)分析算法采用层序遍历结构通过双端队列的入队与出队操作对二叉树中的每个物理节点进行且仅进行一次访问。在内部for循环中弹出一个节点、索引边界比对、以及子节点的非空校验与入队操作均为常数阶操作 O(1)。若整棵树包含 n 个节点总计执行的基本操作次数与 n 呈严格的线性正比关系。结论时间复杂度为 O(n)实现了对全树拓扑结构进行横向扫描的最优时间开销。2. 空间复杂度O(w)分析算法的额外内存空间开销由双端队列q在整个运行周期内同时容纳的最大节点数量决定。队列中同时存在的节点数不会超过二叉树的最大宽度 w。在最坏情况下二叉树为满二叉树其最底层包含约 n/2 个节点此时宽度 w 趋近于 n 阶空间复杂度表现为 O(n)在最好情况下二叉树退化为单链表每层仅有一个节点w 为 1空间复杂度优化为 O(1)。结论空间复杂度表示为 O(w)其中 w 为二叉树最大宽度内存空间的峰值占用完全受控于树的横向拓扑形态。