资讯详情 LeetCode-Go 题解:199. Binary Tree Right Side View —— 基于层序遍历的二叉树右视图
📅 2026/11/17 2:31:02
LeetCode-Go 题解199. 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 199「二叉树的右视图」Binary Tree Right Side View这一经典层序遍历变种题给定一棵二叉树想象自己站在树的右侧按从上到下的顺序返回你所能看到的节点值。文章以 LeetCode-Go 仓库中 199. Binary Tree Right Side View.go 的官方实现为主线逐行剖析基于队列的 BFS 解法并结合 测试用例 与 结构体工具库 深入讲解其底层原理、遮挡问题的本质以及与第 102、107 题之间的关联。读完本文你将能够独立写出任意版本的树的某一侧视图解法并掌握层序遍历队列技巧的通用范式。题目描述Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.从二叉树的右侧观察这棵树返回从上到下你能看到的节点值序列。需要注意某些节点会被同层更靠右的节点遮挡因此每一层只会输出一个节点。示例Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 --- / \ 2 3 --- \ \ 5 4 ---树的结构为根节点 1左子树 2其右孩子 5右子树 3其右孩子 4。站在右侧看过去第 0 层只能看到根节点1第 1 层节点2被同层的3遮挡只能看到3第 2 层节点5被同层的4遮挡只能看到4。因此答案为[1, 3, 4]。题目核心从右侧观察意味着什么从右往左看一棵树这一表述本质上等价于按层从上到下取每一层最右侧的节点值。这是理解本题的关键也是原文档 Problem Summary 中特别强调注意有遮挡some nodes may be blocked from view的原因。从源码结构看只要把一棵树按层序遍历完整展开每一层的最后一个节点即 BFS 队列中该层末尾的元素就是右侧视角能看到的节点。反之若要求左视图则只需取每一层的第一个节点若要求之字形视图则交替取首尾节点。这一观察为后续所有侧视图类题目提供了统一的解题框架。解题思路层序遍历 取每层最右元素本题的标准解法是层序遍历level-order traversal的变种原文档给出的思路可归纳为两点按照层序把每层的元素全部遍历出来依次取每一层的最右边的元素汇总即为答案。实现上用一个队列即可完成这也是 README.md 与官方文档共同推荐的方式。具体到仓库中的实现还隐藏着一个巧妙的优化并不需要把每层元素显式收集成二维数组再取末位而是在 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 }逐行解读如下行号代码说明res : []int{}初始化结果切片按层顺序存放每一层最右侧节点的值if root nil { return res }空树直接返回空切片避免后续访问 nil 指针queue : []*TreeNode{root}用 Go 切片模拟队列初始只含根节点n : len(queue)关键技巧记录当前层的节点数量。进入内层循环前队列中恰好存放着完整的一整层节点内层for i : 0; i n; i只处理当前层的n个节点将它们的左右孩子追加到队尾新追加的节点属于下一层不会在本轮被消费res append(res, queue[n-1].Val)当前层最后一个节点下标n-1即该层最右侧节点正是右视图中该层可见的节点queue queue[n:]一次性弹出当前层全部n个节点队列收缩为下一层节点继续外层循环为什么queue[n-1]一定是该层最右侧节点内层循环按i从0到n-1的顺序遍历当前层节点而层序遍历严格遵循先左后右的入队顺序。因此对于当前层这n个节点它们从左到右排列在队列下标0..n-1区间内下标n-1对应的必然是该层最右侧的节点。若该节点存在左/右孩子孩子已在同轮循环中追加到队尾不影响本层结论。关于queue[i]下标引用的说明内层循环直接使用queue[i]而非弹队首配合queue queue[n:]批量裁剪避免了频繁的切片头部弹出操作带来的内存拷贝是 Go 语言实现 BFS 的典型高效写法。这种记录当前层长度 → 消费固定数量 → 批量出队的模式也正是 102. Binary Tree Level Order Traversal 中levelOrder采用的同款范式。与第 102、107 题的关联原文档明确指出第 102 题和第 107 题都是按层序遍历的题目它们与本题共享同一套队列层序遍历内核区别仅在于对每层结果的处理方式题号题目层序遍历内核差异点102Binary Tree Level Order Traversal队列 BFS输出完整的每层节点列表[[3],[9,20],[15,7]]107Binary Tree Level Order Traversal II队列 BFS自底向上输出即先调levelOrder再反转结果199本题Binary Tree Right Side View队列 BFS只取每层最后一个节点对比可见102 题在每层循环中把整层节点收集进tmp切片107 题在此基础上对结果整体反转而 199 题则更进一步——连临时切片都省去直接取queue[n-1].Val。三题由浅入深正好展示了层序遍历收集整层 → 变换顺序 → 按位置取值的三级演化掌握本题即可举一反三。仓库测试用例验证仓库为本题提供了完整的单元测试见 199. Binary Tree Right Side View_test.go共覆盖 4 组用例输入层序数组期望输出覆盖点[]空树[]空树边界[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)将层序整数数组还原为二叉树再调用rightSideView断言结果。其中structures.NULL常量定义为-1 63见 structures/TreeNode.go用于在数组中标记空节点占位。以第 4 组用例为例[1,2,3,4,NULL,NULL,5]还原出的树为1 / \ 2 3 / \ 4 5站在右侧观察第 0 层见1第 1 层2被3遮挡见3第 2 层4被5遮挡见5输出[1,3,5]。这组用例精准验证了被遮挡节点不输出这一核心语义——即便最右侧可见节点位于左子树一侧的深层算法依然正确。测试辅助工具Ints2TreeNode测试用例依赖仓库公共结构体工具 structures/TreeNode.go 中的Ints2TreeNode将层序数组还原为指针树。其实现同样采用队列func Ints2TreeNode(ints []int) *TreeNode { n : len(ints) if n 0 { return nil } root : TreeNode{Val: ints[0]} queue : make([]*TreeNode, 1, n*2) queue[0] root i : 1 for i n { node : queue[0] queue queue[1:] if i n ints[i] ! NULL { node.Left TreeNode{Val: ints[i]} queue append(queue, node.Left) } i if i n ints[i] ! NULL { node.Right TreeNode{Val: ints[i]} queue append(queue, node.Right) } i } return root }该函数从左到右依次为每个父节点挂接左、右孩子遇到NULL占位符则跳过。理解了它就理解了 LeetCode 输入数组层序序列化格式与内存中二叉树的对应关系——测试中p.one数组的第一个元素恒为根节点随后每两个元素为一对左右孩子。该工具同时被本仓库数百道二叉树题目的测试用例复用。复杂度分析时间复杂度O(n)。每个节点恰好入队、出队各一次其中n为二叉树节点总数。空间复杂度O(n)。最坏情况下如完全二叉树的最底层队列中同时存放的节点数可达 O(n/2)即 O(n) 量级若不考虑输出数组res本身辅助空间同样为队列所占用的 O(n)。变体与延伸掌握本题的每层取末位思想后可以快速推导出同类变体左视图把res append(res, queue[n-1].Val)改为res append(res, queue[0].Val)其余代码完全不变之字形/锯齿形视图交替取每层的首节点与末节点树的左/右侧最大小值序列对每层节点做聚合运算后取极值例如 515. Find-Largest-Value-in-Each-Tree-Row 正是取每层最大值。运行与验证本仓库为 Go 模块项目见根目录 go.mod可按如下方式在本地运行本题测试# 在仓库根目录执行运行 199 题测试 go test -v -run Test_Problem199 ./leetcode/0199.Binary-Tree-Right-Side-View/测试输出会打印每组输入的还原结果与实际输出例如【input】:[3 9 20 -9223372036854775808 -9223372036854775808 15 7] 【output】:[3 20 7]其中-9223372036854775808即structures.NULL-1 63的数值形式对应 LeetCode 输入中的null占位符。仓库根目录的 gotest.sh 提供了批量跑全部测试的脚本可供整体回归验证。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考