本文概览：本文以LeetCode题目"二叉树的右视图"为例，讲解为什么DFS局部思考会踩坑（左子树高于右子树时漏节点），以及如何用BFS层序遍历取每层最后一个节点得到右视图

一、题目

二叉树的右视图题目

二、题目分析

题目要求：站在二叉树右侧看过去，能看到哪些节点，从上到下依次返回

比如：

1
2
3
4
5
6
7
        1
       / \
      2   3
       \   \
        5   4

右视图：[1, 3, 4]

思路概览

Java 实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public List<Integer> rightSideView(TreeNode root) {
    // 结果列表
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    // 层序遍历
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            // 当前节点
            TreeNode node = q.poll();
            // 左子树入队
            if (node.left != null) {
                q.add(node.left);
            }
            // 右子树入队
            if (node.right != null) {
                q.add(node.right);
            }
            // 最后一个节点入结果
            if (i == size - 1) {
                res.add(node.val);
            }
        }
    }
    return res;
}

思路简要说明

  • 用 BFS 层序遍历，每遍历到一层的最后一个节点（i == size - 1）就加入结果
  • size 在 for 循环外记录，保证每一轮 for 循环只处理当前层的节点

三、思路详解

容易踩坑的思路：DFS 贪心走右子树

做这道题最容易犯的错误，就是带入前几题的思路：对每个节点来判断，如果有右子树就添加右子树，没有就添加左子树，如果左子树也没有就什么都不添加

这种思路犯了局部思考忽略全局的错误

在左右子树高度一致的情况下没问题：

1
2
3
4
5
6
7
8
        1
       / \
      2   3
       \   \
        5   4

贪心走右：1 → 3 → 4
右视图：  [1, 3, 4]  ✓ 没问题

但当左子树高度大于右子树时，问题就出现了：

1
2
3
4
5
6
7
8
9
10
11
12
13
            1
           / \
          2   3
           \   \
            5   4
           /
          6

贪心走右：1 → 3 → 4，然后 3、4 都没有右子树了，结束
右视图：  [1, 3, 4]  ✗ 错了！

正确右视图：[1, 3, 4, 6]
  第4层只有左子树下的节点6，从右边看过去依然能看到它

为什么会错？ 因为人可以站在全局视角看到左子树还有节点 6，但计算机只能看到每个节点的左右孩子。贪心走右子树的 DFS 只能看到某一条路的最底端，看不到全局。右子树走完了就以为结束了，实际上左子树更深处还有节点，那些节点的最右节点也是右视图的一部分

所以问题的关键是：怎么拿到每一层的最后一个节点——这不是 DFS 能做的，需要 BFS

正确思路：BFS 层序遍历取每层最后一个

换一种思路，其实就是 BFS 层序遍历。站在右侧看，每一层能看到的就是该层最右边的那个节点。所以只需要遍历每一层，把每一层的最后一个节点放进结果就好了

问题就变成：怎么得到每一层的最后一个节点？

这和我们上一篇"二叉树的层序遍历"是同一套机制：

  1. 创建一个队列，根节点入队
  2. 每轮开始前，先用 size 记录当前队列大小（即当前层的节点数）
  3. for 循环遍历 size 次，逐个出队当前层的节点，出队的同时把左右孩子入队
  4. 当遍历到第 size 次（即 i == size - 1）时，当前节点就是这一层的最后一个节点，加入结果

为什么 size 要在 for 循环外记录？ 因为 for 循环中会往队列加入新节点（下一层的孩子），如果用 queue.size() 做循环条件，大小会不断变化，一轮就处理了多层的节点，分不清层界线。提前用 size 固定下来，for 循环只处理当前层的节点，等这一轮结束，队列里剩下的就是下一层的节点

图解完整过程

以这棵树为例：

1
2
3
4
5
6
7
8
9
            1
           / \
          2   3
           \   \
            5   4
           /
          6

右视图：[1, 3, 4, 6]

初始：队列 = [1]

第 1 轮（第 1 层，size=1）：

1
2
3
4
5
6
7
8
队列：[1]

i=0：出队 1
  左孩子 2 入队
  右孩子 3 入队
  i == size-1 (0 == 0) → 是最后一个，加入结果 res=[1]

队列变为：[2, 3]

第 2 轮（第 2 层，size=2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
队列：[2, 3]

i=0：出队 2
  没有左孩子
  右孩子 5 入队
  i != size-1，不是最后一个

队列变为：[3, 5]

i=1：出队 3
  没有左孩子
  右孩子 4 入队
  i == size-1 (1 == 1) → 是最后一个，加入结果 res=[1, 3]

队列变为：[5, 4]

第 3 轮（第 3 层，size=2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
队列：[5, 4]

i=0：出队 5
  左孩子 6 入队
  没有右孩子
  i != size-1，不是最后一个

队列变为：[4, 6]

i=1：出队 4
  没有左孩子
  没有右孩子
  i == size-1 (1 == 1) → 是最后一个，加入结果 res=[1, 3, 4]

队列变为：[6]

第 4 轮（第 4 层，size=1）：

1
2
3
4
5
6
7
8
队列：[6]

i=0：出队 6
  没有左孩子
  没有右孩子
  i == size-1 (0 == 0) → 是最后一个，加入结果 res=[1, 3, 4, 6]

队列变为：[]（空）

队列空了，遍历结束。最终结果：[1, 3, 4, 6]

注意第 4 层——节点 6 是左子树底下的节点，但它依然是第 4 层唯一的节点，从右边看过去能看到它。BFS 逐层扫描，不会像 DFS 贪心走右那样漏掉它

和层序遍历的关系

这道题和上一篇"二叉树的层序遍历"是同一套 BFS 框架，唯一区别：

层序遍历 二叉树的右视图
每层处理 所有节点都加入结果 只加入每层最后一个节点
判断条件 无条件加入 if (i == size - 1) 才加入

核心都是用 size 控制每层范围，用 for 循环精确处理当前层

复杂度分析

  • 时间复杂度：O(n)，每个节点入队一次、出队一次
  • 空间复杂度：O(n)，队列最多存放一层节点，最坏情况约 n/2 个