企业官网建设流程全解析

LeetCode-Go 题解 0199：二叉树右视图（Binary Tree Right Side View）层序遍历实现详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 LeetCode-Go 仓库中 leetcode/0199.Binary-Tree-Right-Side-View/README.md 为核心骨架，结合仓库内的 Go 源码实现与单元测试，深入讲解 LeetCode 第 199 题「二叉树右视图」的层序遍历解法。读完本文，你将掌握"从右侧观察二叉树"的建模方式、基于队列的单层快照 BFS 技巧，以及如何在 LeetCode-Go 项目中运行与验证该题解。

题目描述

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

示例：

Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <---

其中<---标记的节点（1、3、4）即为从右侧看到的节点。

题目大意

从右边看一棵树，输出看到的数字。注意有遮挡：从右侧观察时，同一层中靠左的节点会被靠右的节点遮住，因此每一层只会输出该层最右侧的那个节点；当某一层只有左子树时，则输出该层最右侧实际存在的节点（例如上例第二层的 3，以及第三层位于 2 右子树上的 5 会被 4 遮挡）。

解题思路：层序遍历的变种

原文档明确指出：这一题是按层序遍历的变种题。核心思路分为两步：

1. 按照层序（Level Order）把每一层的节点全部遍历出来；
2. 依次取出每一层的最右边一个节点的值，组成结果数组。

实现上只需要一个队列即可完成，不需要额外的递归或栈结构。此外，原文档还提示了本系列题目的归类关系：第 102 题（Binary Tree Level Order Traversal）和第 107 题（Binary Tree Level Order Traversal II）都是按层序遍历的题目，本题是这一系列的一个变种——层序遍历后不再收集整层，而是只取每层末尾节点。

仓库源码实现：基于队列快照的 BFS

仓库中 199. Binary Tree Right Side View.go 给出了完整实现：

package leetcode import ( "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func rightSideView(root *TreeNode) []int { res := []int{} if root == nil { return res } queue := []*TreeNode{root} for len(queue) > 0 { n := len(queue) for i := 0; i < n; i++ { if queue[i].Left != nil { queue = append(queue, queue[i].Left) } if queue[i].Right != nil { queue = append(queue, queue[i].Right) } } res = append(res, queue[n-1].Val) queue = queue[n:] } return res }

代码中有两个值得注意的设计点：

• n := len(queue)层快照：进入每层处理前先记录当前队列长度n。内层for i := 0; i < n; i++只处理本层原有的n个节点，同时把它们的左右孩子追加到队尾，从而把"下一层节点"与"当前层节点"严格区分开；
• res = append(res, queue[n-1].Val)取层末节点：本层节点在队列中的下标范围是[0, n-1]，因此queue[n-1]就是本层最右侧的节点，将其值写入结果数组；
• queue = queue[n:]丢弃已处理层：通过切片操作原地收缩队列，下一轮循环便从新层开始。

类型别名与数据结构

解法开头通过type TreeNode = structures.TreeNode将节点类型别名指向仓库公共结构 structures/TreeNode.go 中定义的结构：

type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

这种"解题文件统一复用公共数据结构"的写法在 LeetCode-Go 仓库中是统一惯例，保证了所有二叉树题目使用一致的节点定义，也方便测试数据的构造与断言。

关键细节：为什么 queue[n-1] 就是每层最右节点

以题目示例[1,2,3,null,5,null,4]为例，逐步模拟队列状态：

1. 初始队列[1]，n = 1，处理节点 1，入队其左右孩子，队列变为[2, 3]；queue[n-1] = queue[0]即节点 1，输出1；
2. 队列[2, 3]，n = 2，依次处理节点 2、3：节点 2 的右孩子 5 入队，节点 3 的右孩子 4 入队，队列变为[5, 4]；queue[n-1] = queue[1]即节点 3，输出3；
3. 队列[5, 4]，n = 2，无孩子入队；queue[1]即节点 4，输出4。

最终得到[1, 3, 4]，与题目预期一致。可以看出，只要保证每层节点在入队时按"先左后右"的顺序追加（源码中先判断Left再判断Right），那么该层在队列中的最后一个元素必然是该层最右侧的可见节点。

边界情况：空树

源码在最开头对root == nil做了判断并直接返回空切片，因此空树场景（测试用例para199{[]int{}}）输出为[]，不会发生空指针解引用。

测试用例与运行验证

仓库配套的单元测试 199. Binary Tree Right Side View_test.go 覆盖了四组场景：

测试代码通过structures.Ints2TreeNode(p.one)把层序整数数组还原为二叉树。该工具函数同样位于 structures/TreeNode.go，它借助队列逐层建树，并用structures.NULL（定义于 structures/TreeNode.go，值为-1 << 63）表示空节点占位，例如数组[1,2,3,NULL,NULL,15,7]中下标 3、4 的两个NULL表示节点 2 没有左右孩子。

在仓库根目录执行以下命令即可运行本题测试：

go test -v ./leetcode/0199.Binary-Tree-Right-Side-View/ -run Test_Problem199

测试通过时会输出：

------------------------Leetcode Problem 199------------------------ 【input】:[] 【output】:[] 【input】:[1] 【output】:[1] 【input】:[3 9 20 0 0 15 7] 【output】:[3 20 7] 【input】:[1 2 3 4 0 0 5] 【output】:[1 3 5]

（说明：NULL = -1 << 63在格式化输出时显示为 0，实际传入Ints2TreeNode的仍是structures.NULL常量。）

复杂度分析

• 时间复杂度：O(n)。每个节点恰好入队、出队各一次，遍历整棵树一遍；
• 空间复杂度：O(n)。队列中最多同时容纳二叉树某一层的全部节点，最坏情况（如满二叉树的最底层）队列大小为 O(n)；结果数组res额外占用 O(h)，其中 h 为树的高度。

关联题目与进阶思考

原文档提示第 102、107 题与本题目同属层序遍历系列：

• 0102.Binary-Tree-Level-Order-Traversal：标准层序遍历，输出每层完整节点列表；
• 0107.Binary-Tree-Level-Order-Traversal-II：自底向上的层序遍历。

作为进阶延伸，本题除了 BFS 队列解法外，还可以用**深度优先遍历（DFS）**实现：先递归右子树、再递归左子树，同时携带深度信息，当某深度第一次被访问时，该节点即为该层最右可见节点。相比 BFS，DFS 解法的空间复杂度可降至 O(h)（递归栈深度），两种思路均值得练习。

源码路径索引

• 题目文档：leetcode/0199.Binary-Tree-Right-Side-View/README.md
• 核心实现：199. Binary Tree Right Side View.go
• 单元测试：199. Binary Tree Right Side View_test.go
• 公共树结构与建树工具：structures/TreeNode.go

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go