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 遮挡。解题思路层序遍历的变种原文档明确指出这一题是按层序遍历的变种题。核心思路分为两步按照层序Level Order把每一层的节点全部遍历出来依次取出每一层的最右边一个节点的值组成结果数组。实现上只需要一个队列即可完成不需要额外的递归或栈结构。此外原文档还提示了本系列题目的归类关系第 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]n 1处理节点 1入队其左右孩子队列变为[2, 3]queue[n-1] queue[0]即节点 1输出1队列[2, 3]n 2依次处理节点 2、3节点 2 的右孩子 5 入队节点 3 的右孩子 4 入队队列变为[5, 4]queue[n-1] queue[1]即节点 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 覆盖了四组场景输入层序数组期望输出覆盖场景[][]空树[1][1]单节点树[3,9,20,NULL,NULL,15,7][3,20,7]完整二叉树[1,2,3,4,NULL,NULL,5][1,3,5]左右子树深度不同的非平衡树测试代码通过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**实现先递归右子树、再递归左子树同时携带深度信息当某深度第一次被访问时该节点即为该层最右可见节点。相比 BFSDFS 解法的空间复杂度可降至 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考