LeetCode-Go 题解 508Most Frequent Subtree Sum 出现次数最多的子树元素和【免费下载链接】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/0508.Most-Frequent-Subtree-Sum/README.md 的题目与思路说明深入讲解 LeetCode 508「出现次数最多的子树元素和」的完整解法。文章以仓库中的 Go 源码实现与测试用例为佐证带读者掌握二叉树后序遍历统计子树和的通用套路、基于哈希表计数选取众数的两种编码风格以及本项目 structures 工具包中二叉树构造与层序遍历数组之间的对应关系。读完本文你将能独立写出该题的最优解并理解 O(n) 时间复杂度的推导过程。一、题目原文与核心概念Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.题目要求给定一棵二叉树的根节点找出出现次数最多的子树元素和。其中子树元素和subtree sum以某个节点为根形成的整棵子树中所有节点值之和包括该节点本身目标统计整棵树所有节点对应的子树元素和找出出现频次最高的值并列处理若多个值出现的频次并列最高则全部返回顺序不限数据范围题目保证任意子树的元素和均在 32 位有符号整数范围内因此求和过程中不会出现整数溢出可以直接使用int累加。题目大意仓库 README 的中文总结为给出二叉树的根找出出现次数最多的子树元素和一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和包括结点本身如果有多个元素出现的次数相同则返回所有出现次数最多的元素不限顺序。二、示例剖析示例 1频次全部为 1全部返回输入树5 / \ 2 -3逐个节点计算子树元素和节点子树元素和计算过程子树和出现频次2叶子221-3叶子-3-315根5 2 (-3)41三个值2、-3、4各出现一次频次并列最高因此全部返回即[2, -3, 4]顺序不限。示例 2存在重复频次只返回众数输入树5 / \ 2 -5逐个节点计算子树元素和节点子树元素和计算过程子树和出现频次2叶子221-5叶子-5-515根5 2 (-5)22值2出现了 2 次-5只出现 1 次因此返回[2]。三、解题思路仓库 README 给出的思路非常精炼核心是三步递归求每个节点的子树和以任意顺序遍历实际采用后序遍历对每个节点计算该节点值 左子树和 右子树和用 map 记录频次以子树和为 key、出现次数为 value遍历完整棵树后得到一张频次表输出频次最多的和遍历频次表找出最大频次若并列则全部输出。由于每个节点的子树和都依赖其左右子树的结果天然适合自底向上的后序遍历先递归处理左右孩子再累加当前节点值并登记频次。整棵树每个节点只被访问一次配合哈希表的 O(1) 读写整体时间复杂度为O(n)n 为节点数空间复杂度为 O(n)哈希表最多记录 n 个不同的子树和。四、源码实现解析仓库在 508. Most Frequent Subtree Sum.go 中给出了两种解法前者不排序、直接维护最大频次后者先收集频次再排序取最大。两种解法思路等价可互为对照。解法一遍历频次表时维护最大频次推荐// 解法一 维护最大频次不用排序 func findFrequentTreeSum(root *TreeNode) []int { memo : make(map[int]int) collectSum(root, memo) res : []int{} most : 0 for key, val : range memo { if most val { res append(res, key) } else if most val { most val res []int{key} } } return res } func collectSum(root *TreeNode, memo map[int]int) int { if root nil { return 0 } sum : root.Val collectSum(root.Left, memo) collectSum(root.Right, memo) if v, ok : memo[sum]; ok { memo[sum] v 1 } else { memo[sum] 1 } return sum }核心设计要点collectSum同时承担两件事返回以root为根的子树和并顺带把该和写入memo频次表。空节点返回0作为递归的终止条件同时保证叶子节点的子树和就是其自身值findFrequentTreeSum在扫描memo时动态维护结果用most记录当前已见过的最大频次。遇到更高频次时重置结果切片遇到相等频次时追加元素这样一轮遍历即可完成筛选完全不需要排序也不依赖 Go map 的遍历顺序边界情况空树时memo为空res保持为空切片符合题目对空输入的语义测试用例中也覆盖了空树返回[]的情况。解法二收集频次后排序取最大// 解法二 求出所有和再排序 func findFrequentTreeSum1(root *TreeNode) []int { if root nil { return []int{} } freMap, freList, reFreMap : map[int]int{}, []int{}, map[int][]int{} findTreeSum(root, freMap) for k, v : range freMap { tmp : reFreMap[v] tmp append(tmp, k) reFreMap[v] tmp } for k : range reFreMap { freList append(freList, k) } sort.Ints(freList) return reFreMap[freList[len(freList)-1]] } func findTreeSum(root *TreeNode, fre map[int]int) int { if root nil { return 0 } if root ! nil root.Left nil root.Right nil { fre[root.Val] return root.Val } val : findTreeSum(root.Left, fre) findTreeSum(root.Right, fre) root.Val fre[val] return val }核心设计要点这里使用了三张表freMap子树和 → 频次、reFreMap频次 → 该频次下的所有子树和反查表、freList所有频次的集合findTreeSum与collectSum逻辑等价只是把叶子节点单独分支提前返回从代码结构上可以推断这是一种对叶子节点子树和即自身值的显式优化最后对freList升序排序取最大频次对应的子树和列表返回。由于sort.Ints的时间复杂度为 O(m log m)m 为不同频次的个数从源码结构看在极端场景下解法二会比解法一多出排序开销这也是注释中强调解法一不用排序的原因该解法对空树单独返回[]int{}与解法一的空切片行为保持一致。两种解法对比小结维度解法一findFrequentTreeSum解法二findFrequentTreeSum1遍历频次表方式单次遍历动态维护最大频次先建反查表再排序取最大是否需要排序否是sort.Ints时间复杂度O(n)O(n m log m)代码风格简洁推荐表结构清晰便于教学对照五、数据结构与工具链支撑题目解法中使用的TreeNode并非在题解文件内自行定义而是直接复用了仓库structures包中的通用二叉树结构体并在文件顶部做了类型别名// TreeNode define type TreeNode structures.TreeNodestructures包在 structures/TreeNode.go 中定义// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }这种设计体现了仓库公共数据结构统一维护、题解文件只关心算法的组织方式所有二叉树类题解如 94、100、102、226 等都复用同一份TreeNode避免了在每个目录里重复定义结构体。同时structures包提供了从层序遍历数组构造二叉树的工具函数 Ints2TreeNode其核心逻辑是以数组首元素为根借助队列按层序为每个节点挂载左右孩子数组中用NULL -1 63表示空节点占位。测试用例正是用它把[]int{5, 2, -3}这样的输入快速转换为题目要求的树结构这也是仓库测试代码能保持高度简洁的原因。六、测试用例验证仓库为本题编写了完整的单元测试位于 508. Most Frequent Subtree Sum_test.go测试入口为Test_Problem508覆盖了以下五组用例输入层序数组期望输出用例意图[]int{}[]int{}空树边界[]int{1, 1}[]int{1, 2}两节点树两个子树和各出现一次[]int{1}[]int{1}单节点树[]int{5, 2, -3}[]int{2, -3, 4}题目示例 1全部返回[]int{5, 2, -5}[]int{2}题目示例 2只返回众数测试代码遵循仓库统一的题解测试模板用question508结构封装para508输入参数与ans508期望答案通过structures.Ints2TreeNode(p.one)构造二叉树再调用findFrequentTreeSum与findFrequentTreeSum1分别验证。需要说明的是示例 1 中期望输出为[2, -3, 4]由于题目允许并列值时任意顺序返回findFrequentTreeSum返回结果的元素顺序与 map 遍历顺序有关因此测试中并未对结果顺序做严格断言而只是调用并打印输出——这也呼应了题目 return all the values with the highest frequency in any order 的约定。七、本地运行与验证在仓库根目录模块名github.com/halfrost/LeetCode-Go见 go.mod下可以单独运行本题的测试验证上述两种解法的正确性go test -v -run Test_Problem508 ./leetcode/0508.Most-Frequent-Subtree-Sum/其中-run Test_Problem508只执行本题的测试函数避免跑完整仓库的数千个用例./leetcode/0508.Most-Frequent-Subtree-Sum/指向本题所在的包目录测试通过 go.mod 中的replace指令将github.com/halfrost/LeetCode-Go/structures重定向到本地./structures目录因此structures.Ints2TreeNode等工具函数可以直接在本仓库内使用无需额外下载依赖。运行后会在终端输出每组输入对应的构造树与两种解法的计算结果方便肉眼对照题目示例。八、小结LeetCode 508 的核心价值在于后序遍历的经典应用子树和的统计天然要求先算孩子再算父亲是二叉树自底向上递归的最佳入门例题之一统计 众数 的组合套路用哈希表统计频次、再筛选最大频次是大量树与数组类题目的通用模板如 501 二叉搜索树中的众数、451 根据字符出现频率排序等均可类比工程化细节仓库通过 structures 包统一管理TreeNode定义与构造工具让每道题解专注于算法本身测试用例覆盖空树、单节点、两节点与题目示例保证了实现的正确性。仓库同时提供了不排序与排序两种风格迥异的实现前者更贴近 O(n) 的最优解后者便于理解频次反查表的数据组织方式读者可以根据自己的学习阶段选择对照阅读。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考