当前位置：首页 > news >正文

【LeetCode 热题 100】199. 二叉树的右视图——（解法一）BFS

news 2025/7/19 6:36:06

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(W) 或 O(N)

整体思路

这段代码旨在解决一个经典的二叉树问题：二叉树的右视图 (Binary Tree Right Side View)。问题要求从右侧观察一个二叉树，并按从上到下的顺序，返回所有能看到的节点的值。

该算法的核心是采用 广度优先搜索 (BFS)，也常被称为 层序遍历 (Level-Order Traversal)。通过逐层遍历树，我们可以轻松地确定每一层的最右侧节点。

其核心逻辑步骤如下：

初始化：
- 处理边界情况：如果树的根节点 root 为空，则直接返回一个空列表。
- 创建一个队列 q 用于实现BFS，并将根节点 root 入队，作为遍历的起点。
- 创建一个列表 ans 用于存储最终的结果。
层序遍历：
- 算法的主体是一个 while 循环，只要队列不为空，就持续进行遍历。每一次 while 循环的迭代，都完整地处理树的一整层。
- 标记层级：在每次 while 循环的开始，通过 int levelSize = q.size() 获取当前队列中的节点数量。这个 levelSize 精确地代表了当前层所包含的节点总数。
- 遍历当前层：接着，一个 for 循环会执行 levelSize 次。这个循环的作用是，将当前层的所有节点全部从队列中取出并处理，同时将它们的子节点（下一层的节点）加入队列。
识别最右侧节点：
- 这是算法最巧妙的部分。在处理每一层之前，声明一个 TreeNode out = null。
- 在 for 循环中，每次从队列中取出一个节点时，都用它来更新 out 变量 (out = q.poll())。
- 因为层序遍历是从左到右处理节点，所以当这个 for 循环结束时，out 变量中存储的必然是当前层被最后一个处理的节点，也就是该层的最右侧节点。
- 在 for 循环结束后，将 out 节点的值 out.val 添加到结果列表 ans 中。
返回结果：
- 当 while 循环结束（即所有层都已遍历完毕），ans 列表中就包含了每一层的最右侧节点的值，将其返回即可。

完整代码

class Solution {/*** 返回二叉树的右视图。* @param root 二叉树的根节点* @return 一个包含右视图节点值的列表*/public List<Integer> rightSideView(TreeNode root) {// ans: 用于存储最终的右视图结果List<Integer> ans = new ArrayList<>();// 处理边界情况：如果树为空，直接返回空列表if (root == null) return ans;// q: 创建一个队列用于实现广度优先搜索（BFS）Queue<TreeNode> q = new ArrayDeque<>();// 将根节点入队，开始遍历q.offer(root);// 当队列不为空时，说明树中还有节点需要处理while (!q.isEmpty()) {// 关键步骤：获取当前层的节点数量int levelSize = q.size();// out: 用于记录当前层最后一个被处理（即最右侧）的节点TreeNode out = null;// 遍历当前层的所有节点for (int i = 0; i < levelSize; i++) {// 从队列头部取出一个节点，并用 out 变量记录它out = q.poll();// 如果该节点有左孩子，将其入队，以备下一层遍历if (out.left != null) q.offer(out.left);// 如果该节点有右孩子，将其入队if (out.right != null) q.offer(out.right);}// for 循环结束后，out 中保存的就是当前层的最右侧节点，// 将其值加入结果列表。ans.add(out.val);}// 返回最终结果return ans;}
}

时空复杂度

时间复杂度：O(N)

节点访问：该算法采用BFS，会访问树中的每一个节点且仅访问一次。
入队出队操作：每个节点都会被入队（offer）一次，也会被出队（poll）一次。队列的这些操作的平均时间复杂度都是 O(1)。
综合分析：
- 整个算法的执行时间主要取决于访问所有节点所需的时间。如果树中有 N 个节点，那么总的时间开销与 N 成正比。
- 因此，总的时间复杂度是 O(N)。

空间复杂度：O(W) 或 O(N)

主要存储开销：算法的额外空间主要由队列 q 占用。
空间大小：队列 q 在任意时刻存储的都是树中某一层的节点。其空间占用的峰值取决于树的最宽层的节点数。设树的最大宽度为 W。
- 在最好的情况下（一个极度倾斜的链状树），W=1，空间复杂度为 O(1)。
- 在最坏的情况下（一个完全二叉树），最后一层包含大约 N/2 个节点，此时 W 与 N 成正比。
结果列表：ans 列表的空间取决于树的高度 H，即 O(H)。在最坏情况下（链状树），H=N。但通常结果列表的空间不计入辅助空间复杂度。