LeetCode: 508. Most Frequent Subtree Sum

 1 year ago
source link: https://mozillazg.com/2021/02/leetcode-508-most-frequent-subtree-sum.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.



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


 /  \
2   -3

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

Examples 2


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




这个思路的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findFrequentTreeSum(self, root):
        # 统计各个子树的 sum 和的次数
        self._sum_count = {}
        # 最常使用的和的次数,最少出现一次
        self._most_frequent_count = 1
        # 最常使用的和的值,应对不止一个结果的情况
        self._most_frequent_count_values = []


        return self._most_frequent_count_values

    def _sum(self, root):
        if root is None:
            return 0

        val = root.val
        left = self._sum(root.left)
        right = self._sum(root.right)

        sum_value = val + left + right
        # 收集子树和并更新 most frequent sum 结果

        return sum_value

    def _update_frequent_sum_count(self, sum_value):
        if sum_value in self._sum_count:
            self._sum_count[sum_value] += 1
            self._sum_count[sum_value] = 1

        count = self._sum_count[sum_value]
        # 收集相同次数的 sum value
        if count == self._most_frequent_count:
        elif count > self._most_frequent_count:
            # most frequent 的宝座换人
            self._most_frequent_count = count
            self._most_frequent_count_values = [sum_value]

About Joyk

Aggregate valuable and interesting links.
Joyk means Joy of geeK