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

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

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

一、题目描述:

image.png

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


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

  1. 出现次数最多的子树元素和 具体是需要我们做些啥呢?
  • 题目给出了一个棵二叉树,二叉树中的节点数据存放的是整型数据
  • 题目要求我们计算子树和,且输出子树和出现次数最多的子树和结果,如果有多个出现次数都是最多,那么一起输出

分析

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

  • 什么是子树和

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

image.png

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

  • 如何遍历二叉树

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

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

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

举个例子,还是上面的图

image.png

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

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

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

按照题目中给出的示例 2

image.png

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

数值 次数 计算情况
2 2 - 2- 2 + 5 + (-5)
-5 1 -5
5 1 5

可以这样用 hash 表来表示

image.png

那么最后一个重要的点就是,咱们在遍历二叉树和计算子树的过程中,记录子树和出现的最大次数,例如上图中的 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
}

四、总结:

image.png

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

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

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

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

欢迎点赞,关注,收藏

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

image.png

好了,本次就到这里

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

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


相关文章
|
4月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
5月前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
5月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
Cloud Native
【刷题日记】450. 删除二叉搜索树中的节点
本次刷题日记的第 53 篇,力扣题为:450. 删除二叉搜索树中的节点,中等
|
Cloud Native
【刷题日记】进阶版本的 19. 删除链表的倒数第 N 个结点
本次刷题日记的第 19 篇,力扣题为:进阶版本的 19. 删除链表的倒数第 N 个结点 ,中等
|
存储 索引 Cloud Native
【刷题日记】498. 对角线遍历
本次刷题日记的第 65 篇,力扣题为:498. 对角线遍历,中等
|
搜索推荐 Cloud Native
【刷题日记】1403. 非递增顺序的最小子序列
【刷题日记】1403. 非递增顺序的最小子序列
LeetCode每日一题——508. 出现次数最多的子树元素和
给你一个二叉树的根结点 root ,请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。
87 0
LeetCode每日一题——508. 出现次数最多的子树元素和
LeetCode每日一题——652. 寻找重复的子树
给定一棵二叉树 root,返回所有重复的子树。
80 0
LeetCode每日一题——652. 寻找重复的子树