⭐ 题目日期：

百度 - 2024/10/23

🌳 题目描述：

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

示例 1:

输出: [0, 2, 6, 11]

🕵🏽 面试评估：

这道题主要考查二叉树的广度优先遍历，二叉树和广度优先遍历均为备战大厂面试中的核心重要知识点，对于基础不错的候选人，此题不涉及复杂的逻辑分析过程，属于送分题。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

问题的核心在于如何从根节点出发将二叉树的所有节点从左至右分层，并依次识别每一层的最后一个节点。

0

1 2

3 4 5 6

7 8 9 10 11

我们借助队列先入先出的特点将当前队列中的节点取出，并分别将其的各个节点的左右节点加入到队列中，这样队列中节点的顺序保持原来的从左到右的顺序。需要注意不能将下一层的节点在当前层取出，我们在取出当前层节点前，先记一下当前层的节点数 size = queue.size(), 然后再做 size 次取出操作，这样就能保证刚刚加入的子节点不会取出，还有取出时，size 如果为 0， 表明当前取出的节点是当前层的最右边的节点，加入到结果列表中即可。

💻代码：

Java

 public List<Integer> rightSideView(TreeNode root) {
     List<Integer> result = new ArrayList<>();
     if (root == null) {
         return result;
     }

     Deque<TreeNode> queue = new LinkedList<>();
     queue.offerLast(root);

     while (!queue.isEmpty()) {
         int size = queue.size();
         while (size > 0) {
             TreeNode cur = queue.pollFirst();
             size--;
             if (size == 0) {
                 result.add(cur.val);
             }
             if (cur.left != null) {
                 queue.offerLast(cur.left);
             }
             if (cur.right != null) {
                 queue.offerLast(cur.right);
             }
         }
     }

     return result;
 }

🚵🏻复杂度分析：

时间复杂度: O(n), 树中的所有节点都被访问两次

空间复杂度: O(n), 存储每一层的节点