LeetCode | 0508. 出现次数最多的子树元素和【Python】

Wonz 2021-01-20 22:14:10
Python github def a tree


Problem

LeetCode

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.

Examples 1 Input:

 5
/ \
2 -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2 Input:

 5
/ \
2 -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

问题

力扣

给你一个二叉树的根结点,请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。

示例 1:

输入:

 5
/ \
2 -3

返回 [2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。

示例 2: 输入:

 5
/ \
2 -5

返回 [2],只有 2 出现两次,-5 只出现 1 次。

提示: 假设任意子树元素和均可以用 32 位有符号整数表示。

思路

DFS

先思考每一个节点需要做的事:该节点值与左右子树的所有节点值相加。
同时,要记录次数。
再遍历子树元素和,取出次数最多的子树元素和。

Python3 代码

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
import collections
res_dic = collections.defaultdict(int)
 # 计算子树元素和
def dfs(node):
 # 递归边界
if not node:
return 0
tmp_sum = dfs(node.left) + node.val + dfs(node.right)
res_dic[tmp_sum] += 1
return tmp_sum
if not root:
return []
dfs(root)
max_cnt = 0
for cnt in res_dic.values():
max_cnt = max(max_cnt, cnt)
return [key for key, cnt in res_dic.items() if cnt == max_cnt]

GitHub 链接

Python

版权声明
本文为[Wonz]所创,转载请带上原文链接,感谢
https://my.oschina.net/wonz/blog/4916947

  1. A series of problems and solutions in Java calling Python
  2. python自动化爬取淘宝商品数据导入execl表格
  3. Using Python to automatically punch in the pin / enterprise wechat
  4. 【分享】python+requests接口测试基础
  5. Python automatically crawls Taobao product data and imports it into excel table
  6. C++/Python描述 628. 三个数的最大乘积
  7. Python的容器有哪些?分别有什么作用?
  8. python+requests接口测试基础
  9. 20 行代码:Serverless 架构下用 Python 轻松搞定图像分类和预测
  10. python+requests接口测试基础
  11. [share] Python + requests interface test foundation
  12. C + + / Python description 628. Maximum product of three numbers
  13. What are Python containers and what are their functions?
  14. Testing foundation of Python + requests interface
  15. 20 lines of code: easy to do image classification and prediction with Python under serverless architecture
  16. Python爬取优质高清壁纸网站:彼岸
  17. Testing foundation of Python + requests interface
  18. 【人生苦短,我学 Python】基础篇——列表(Day8)
  19. Python crawls high quality HD Wallpaper website: the other side
  20. Python图像增强与特效-利用百度AI进行黑白图像上色
  21. 【七天搞定Python】day01.Python环境配置、pip、IDE、注释、变量,数据类型、标识符/关键字、输出、输入
  22. Life is short, I learn Python
  23. Python image enhancement and special effects - using Baidu AI to color black and white images
  24. Python environment configuration, Pip, IDE, comment, variable, data type, identifier / keyword, output, input
  25. 为什么说Python是最伟大的语言?看图就知道了 - 知乎
  26. Why is Python the greatest language? Just look at the picture. - Zhihu
  27. 通过创建视频游戏来学习 Python
  28. Learn Python by creating video games
  29. Python3版本下创建计算给定日期范围内工作日方法
  30. Creating a method to calculate working days within a given date range in Python 3
  31. 图解爬虫,用几个最简单的例子带你入门Python爬虫
  32. Graphical crawler, with a few of the simplest examples to take you to the introduction of Python crawler
  33. python+requests基础知识
  34. Basic knowledge of Python + requests
  35. python自定义windowsr日志支持文件分割
  36. python+requests基础知识
  37. Python custom Windowsr log supports file segmentation
  38. Basic knowledge of Python + requests
  39. 高级测试 | Python笔试题
  40. 火了!开源的 Python 抢票神器,过年回家就看这一波了!
  41. Python 爬虫进阶 - 前后端分离有什么了不起,过程超详细!
  42. 【python】使用pip提示ModuleNotFoundError
  43. 【python】虚拟环境搭建
  44. Advanced test | Python written test questions
  45. Fire! Open source Python ticket grabbing artifact, come home to see this wave of New Year!
  46. Python crawler advanced - before and after the end of the separation of what great, super detailed process!
  47. [Python] prompt modulenotfounderror with PIP
  48. Building a virtual environment
  49. Serverless 架构下用 Python 轻松搞定图像分类和预测
  50. Easy image classification and prediction with Python under serverless architecture
  51. python协程爬取某网站的老赖数据
  52. Python coroutine crawls Laolai data of a website
  53. 使用Python分析姿态估计数据集COCO的教程
  54. Using Python to analyze the data set coco of attitude estimation
  55. win环境 python3 flask 上手整理 环境搭建(一)
  56. Getting started with win environment python3 flash
  57. Python实现一个论文下载器,赶紧收藏
  58. win环境 python3 flask 上手整理 快速上手-基础操作(二)
  59. Python 中常见的配置文件写法
  60. Python to achieve a paper Downloader, quickly collect