Leetcode | 0508

Wonz 2021-01-20 22:19:10



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:

/ \
2 -3

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

Examples 2 Input:

/ \
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.


Power button

Give you a root node of binary tree , Please find out the subtree elements and . Of a node 「 Subtree elements and 」 It is defined as the sum of the elements of all nodes in the binary tree with the node as the root ( Including the node itself ).

You need to return the most frequent subtree elements and . If more than one element appears the same number of times , Returns all the most frequent subtree elements and ( Unlimited order ).

Example 1:

Input :

/ \
2 -3

return [2, -3, 4], All values appear only once , Returns all values in any order .

Example 2: Input :

/ \
2 -5

return [2], Only 2 Twice ,-5 Only appear 1 Time .

Tips : Suppose any subtree element sum can be used 32 Bit signed integers indicate .



 Think about what each node needs to do first : The node value is added to all the node values of the left and right subtrees .
meanwhile , To record the number of times .
Then traverse the subtree elements and , The subtree elements and .

Python3 Code

# 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)
 # Compute subtree elements and 
def dfs(node):
 # Recursive boundary 
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 []
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 link



  1. 【七天搞定Python】day01.Python环境配置、pip、IDE、注释、变量,数据类型、标识符/关键字、输出、输入
  2. Life is short, I learn Python
  3. Python image enhancement and special effects - using Baidu AI to color black and white images
  4. Python environment configuration, Pip, IDE, comment, variable, data type, identifier / keyword, output, input
  5. 为什么说Python是最伟大的语言?看图就知道了 - 知乎
  6. Why is Python the greatest language? Just look at the picture. - Zhihu
  7. 通过创建视频游戏来学习 Python
  8. Learn Python by creating video games
  9. Python3版本下创建计算给定日期范围内工作日方法
  10. Creating a method to calculate working days within a given date range in Python 3
  11. 图解爬虫,用几个最简单的例子带你入门Python爬虫
  12. Graphical crawler, with a few of the simplest examples to take you to the introduction of Python crawler
  13. python+requests基础知识
  14. Basic knowledge of Python + requests
  15. python自定义windowsr日志支持文件分割
  16. python+requests基础知识
  17. Python custom Windowsr log supports file segmentation
  18. Basic knowledge of Python + requests
  19. 高级测试 | Python笔试题
  20. 火了!开源的 Python 抢票神器,过年回家就看这一波了!
  21. Python 爬虫进阶 - 前后端分离有什么了不起,过程超详细!
  22. 【python】使用pip提示ModuleNotFoundError
  23. 【python】虚拟环境搭建
  24. Advanced test | Python written test questions
  25. Fire! Open source Python ticket grabbing artifact, come home to see this wave of New Year!
  26. Python crawler advanced - before and after the end of the separation of what great, super detailed process!
  27. [Python] prompt modulenotfounderror with PIP
  28. Building a virtual environment
  29. Serverless 架构下用 Python 轻松搞定图像分类和预测
  30. Easy image classification and prediction with Python under serverless architecture
  31. python协程爬取某网站的老赖数据
  32. Python coroutine crawls Laolai data of a website
  33. 使用Python分析姿态估计数据集COCO的教程
  34. Using Python to analyze the data set coco of attitude estimation
  35. win环境 python3 flask 上手整理 环境搭建(一)
  36. Getting started with win environment python3 flash
  37. Python实现一个论文下载器,赶紧收藏
  38. win环境 python3 flask 上手整理 快速上手-基础操作(二)
  39. Python 中常见的配置文件写法
  40. Python to achieve a paper Downloader, quickly collect
  41. Python批量 png转ico
  42. 使用line_profiler对python代码性能进行评估优化
  43. 使用line_profiler对python代码性能进行评估优化
  44. Getting started with Python 3 flash in win environment
  45. Common ways to write configuration files in Python
  46. Python会在2021年死去吗? Python 3.9最终版本的回顾
  47. Python batch PNG to ICO
  48. Using line_ Profiler evaluates and optimizes the performance of Python code
  49. Using line_ Profiler evaluates and optimizes the performance of Python code
  50. Will Python die in 2021? A review of the final version of Python 3.9
  51. Python3 SMTP send mail
  52. Understanding closures in Python: getting started with closures
  53. Python日志实践
  54. Python logging practice
  55. [python opencv 计算机视觉零基础到实战] 十、图片效果毛玻璃
  56. [python opencv 计算机视觉零基础到实战] 九、模糊
  57. 10. Picture effect ground glass
  58. [Python opencv computer vision zero basis to actual combat] 9. Fuzzy
  59. 使用line_profiler對python程式碼效能進行評估優化
  60. Using line_ Profiler to evaluate and optimize the performance of Python code