二叉树右视图怎么求？ - AIGC面试刷题网

简化版

右视图就是每一层最右边能看到的节点。可以 BFS 按层遍历，每层取最后一个节点；也可以 DFS 先访问右子树，第一次到达某个深度的节点就是右视图节点，时间 O(n)。

详细版

BFS 写法最直接：每轮固定当前层 size，循环到第 size - 1 个节点时加入答案。DFS 写法则维护深度，如果 depth == ans.size()，说明这个深度第一次被访问；只要递归顺序是根、右、左，第一次访问到的就是该层最右节点。

List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) ans.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return ans;
}

不要理解成“所有右孩子”。如果某层没有右孩子，左侧节点也可能成为从右边看到的节点。

完整版教学

一、右视图看的是每层最后露出来的节点

右视图不是沿着 root.right.right.right 走一条链。它表示站在树右侧看过去，每一层最后能被看到的节点。某一层如果没有更靠右的节点，那么左子树里的节点也可能出现在右视图里。

    1
   / \
  2   3
   \
    5

右视图: [1,3,5]

第 3 层的 5 虽然不是右孩子链上的节点，但它是这一层最右的节点，所以应该被看到。

二、BFS 的思路：每层取最后一个

层序遍历天然按层组织节点。每轮开始时 size 固定当前层节点数，循环中第 size - 1 个出队节点就是当前层最右边的节点。只要入队顺序保持左孩子先、右孩子后，队列中当前层的顺序就是从左到右。

第 0 层: [1]      -> 取 1
第 1 层: [2,3]    -> 取 3
第 2 层: [5]      -> 取 5

这种写法最容易解释，也最不依赖递归深度。面试中如果想快速给出稳定代码，BFS 是首选。

三、DFS 的思路：右优先的第一次到达

DFS 也可以做。关键是维护深度，并且先访问右子树。如果某个深度还没有答案，当前节点就是从右侧看该深度第一个遇到的节点，因此加入答案。之后再访问左子树，即使同深度还有节点，也不会覆盖。

void dfs(TreeNode node, int depth, List<Integer> ans) {
    if (node == null) return;
    if (depth == ans.size()) ans.add(node.val);
    dfs(node.right, depth + 1, ans);
    dfs(node.left, depth + 1, ans);
}

这个写法的本质是“根右左”的先序遍历。depth == ans.size() 是判断第一次到达该层的简洁条件。

四、为什么不能只沿右指针走

只沿右指针走会漏掉右子树缺失时由左子树补位的节点。比如 1 -> right 3 没有下一层，但 1 -> left 2 -> right 5 存在，那么第 3 层能看到的是 5。右视图考察的是每层相对位置，不是节点指针名称。

错误想法	反例	正确理解
只走右孩子	右链断了但左边还有更深节点	每层最右节点
只收集右孩子	根的左孩子可能在某层可见	层级优先
DFS 左优先	会得到左视图	右视图要右优先

这个区分是面试常追问点，因为它能看出你是否真正理解“视图”的含义。

五、复杂度比较

BFS 和 DFS 都要访问每个节点，时间复杂度都是 O(n)。BFS 的额外空间取决于最大宽度 w，最坏 O(n)；DFS 的额外空间取决于树高 h，最坏也是 O(n)，平衡树下是 O(log n)。两者输出数组长度都是树高，不计入或单独说明均可。

BFS: queue <= 最大宽度
DFS: call stack <= 最大高度

如果树可能特别深，递归 DFS 有栈溢出风险；如果树特别宽，BFS 队列会更占内存。常规面试里二者都可以接受。

六、常见误区与追问

记忆钩子：右视图不是右孩子链，而是“每一层排队时最后站出来的人”。

误区：只沿着 root.right 走。 右链断开时，左子树深层节点也可能出现在右视图中。
误区：BFS 不需要按层。 不按层就无法知道每层最后一个节点是谁。
误区：DFS 左优先也能得到右视图。 左优先第一次到达深度的是左视图节点。
追问：怎么求左视图？ BFS 每层取第一个，或 DFS 根左右并取每层第一次到达的节点。
追问：怎么求俯视图？ 俯视图通常要维护水平距离，已经不是单纯按深度取节点。
追问：如果节点值重复怎么办？ 不影响，视图按节点位置决定，不靠值去重。

七、加强记忆

右视图可以用两个口令记：BFS 是“每层最后一个”，DFS 是“右优先第一次”。BFS 依赖 size 固定层边界，DFS 依赖 depth == ans.size() 判断首次到达。只要不把右视图误解成右孩子链，代码通常就很稳。

简化版

详细版