【刷题日记】508. 出现次数最多的子树元素和

本次刷题日记的第 70 篇，力扣题为：508. 出现次数最多的子树元素和，中等

一、题目描述：

咱今天不做字符串的题了，今天来做做每日一题的二叉树题目，508. 出现次数最多的子树元素和

二、这道题考察了什么思想？你的思路是什么？

508. 出现次数最多的子树元素和 具体是需要我们做些啥呢？

• 题目给出了一个棵二叉树，二叉树中的节点数据存放的是整型数据
• 题目要求我们计算子树和，且输出子树和出现次数最多的子树和结果，如果有多个出现次数都是最多，那么一起输出

分析

一起来看这个题，既然是要计算子树的和，那么必然是要遍历咱们的二叉树了，那么我们先要解决这两个事情：

• 什么是子树和

子树和，题目中也有说到，以某个节点为根节点的二叉树，二叉树上的所有节点之和，就是子树和

例如上述的一颗二叉树，红框框住的位置都是属于子树，换句话说，对于上述二叉树，咱们要计算的就是每一个红框中的节点数据和，最终来梳理一下出现的数据和次数最多的数据是哪一个，便输出即可

• 如何遍历二叉树

子树和知道了之后，那么我们需要如何遍历二叉树呢？

遍历二叉树很简单，咱们通常知道的有：

• 前序遍历 - 先遍历根节点，再遍历左节点，最后遍历右节点
• 中序遍历 - 先遍历左节点，再遍历根节点，最后遍历右节点
• 后序遍历 - 先遍历左节点，再遍历右节点，最后遍历根节点

举个例子，还是上面的图

• 前序遍历 - [5,2,3,6,4]
• 中序遍历 - [3,2,5,6,4]
• 后序遍历 - [3,2,4,6,5]

看到这里，那么就都知道子树和，以及如何遍历二叉树了，那么接下来就是咱们子树和如何存储和计数的事情了

那么有没有发现，根据题意，我们知道，子树和存在的数字有多个，且会出现重复，我们还需要记录每个子树和出现的次数，那么看到这里很容易就要想到 hash 表才对

按照题目中给出的示例 2

简单一看，我们知道子树和有这几种情况：

可以这样用 hash 表来表示

那么最后一个重要的点就是，咱们在遍历二叉树和计算子树的过程中，记录子树和出现的最大次数，例如上图中的 2

最终咱们遍历，hash 表中值为 2 的 key 有多少个，对应加入到结果集中即可

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处需要注意几个点

• 正确遍历二叉树
• 正确计算并记录好子树和的次数

编码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findFrequentTreeSum(root *TreeNode) []int {
    help := make(map[int]int, 0)
    maxCnt := 0
    var dfs func (node *TreeNode) int 
    dfs = func (node *TreeNode) int {
        if node == nil {
            return 0
        }
        sum := node.Val + dfs(node.Left) + dfs(node.Right)
        help[sum]++
        // 记录子树和出现的最大次数
        if help[sum] > maxCnt {
            maxCnt = help[sum]
        }
        return sum
    }
    dfs(root)
    res := make([]int, 0)
    for num,cnt := range  help {
        if cnt == maxCnt {
            res = append(res, num)
        }
    }
    return res
}

四、总结：

很明显，这样的实现方式时间复杂度是 O(n) ，咱们遍历了给出二叉树的所有节点

另外，空间复杂度 也是 O(n) ，咱们引入了一个 hash 表，占空了 O(n) 级别的消耗空间

原题地址：508. 出现次数最多的子树元素和

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~