LeetCode LCR 046. 二叉树的右视图

Categories:

题目描述
思路分析
1. 解法一：BFS 层序遍历（推荐）
2. 解法二：DFS 深度优先搜索
相似题目

题目描述

✅ LCR 046. 二叉树的右视图

思路分析

解法一：BFS 层序遍历（推荐）

核心思路：

右视图 = 每层最后一个节点。BFS 按层遍历，记录每层最后一个节点的值。

推导过程：

用队列进行层序遍历，每次处理一整层（size = queue.size()）

遍历当前层时，当 i == size - 1（最后一个节点），加入结果

将左右子节点依次入队，供下一层使用

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，每个节点恰好访问一次

空间复杂度：O(n)，队列最多存储一层的节点（最宽层最多 n/2 个节点）

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 每层最后一个节点加入结果
                if (i == size - 1) {
                    res.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return res;
    }
}

func rightSideView(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        size := len(queue)

        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]

            // 每层最后一个节点加入结果
            if i == size-1 {
                res = append(res, node.Val)
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }

    return res
}

解法二：DFS 深度优先搜索

核心思路：

右视图 = 每层从右侧看到的第一个节点。DFS 时优先遍历右子树，每层第一次到达时记录该节点值，即为该层最右侧可见节点。

推导过程：

维护全局结果数组 res 和当前已记录的最大深度 maxDepth

DFS 遍历时，若当前深度 depth > maxDepth，说明是该层第一次到达，将节点值加入结果，更新 maxDepth

优先递归右子树，再递归左子树，保证每层第一次到达的节点是最右侧的节点

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归栈深度最大为 h（最坏情况退化为链表时 h = n）

class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 1);
        return res;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        // 每层第一次到达（优先右子树），记录节点值
        if (depth > res.size()) {
            res.add(node.val);
        }
        // 优先遍历右子树，再遍历左子树
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
}

var res []int
var maxDepth int

func rightSideView(root *TreeNode) []int {
    res = []int{}
    maxDepth = 0
    dfs(root, 1)
    return res
}

func dfs(node *TreeNode, depth int) {
    if node == nil {
        return
    }
    // 每层第一次到达（优先右子树），记录节点值
    if depth > maxDepth {
        res = append(res, node.Val)
        maxDepth = depth
    }
    // 优先遍历右子树，再遍历左子树
    dfs(node.Right, depth+1)
    dfs(node.Left, depth+1)
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS 层序遍历基础
103. 二叉树的锯齿形层序遍历	中等	BFS 变向遍历
513. 找树左下角的值	中等	BFS 最后一层第一个（左视图）
637. 二叉树的层平均值	简单	BFS 层级统计
515. 在每个树行中找最大值	中等	BFS 层级统计
116. 填充每个节点的下一个右侧节点指针	中等	BFS 层级连接

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/21997854