LeetCode: 508. Most Frequent Subtree Sum

题目

原题地址：https://leetcode.com/problems/most-frequent-subtree-sum/

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.

题目大意是，求二叉树中出现频次最高的子树和（求所有可能的子树的节点的和，找出这些和值中出现次数最多的值（不一定只有一个））

解法

递归求所有子树的和，在求和的过程中收集所有可能子树的和，然后进行比较，找出出现次数最多的那个和值。

这个思路的 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 = []

        self._sum(root)

        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 结果
        self._update_frequent_sum_count(sum_value)

        return sum_value

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

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

Comments