0508：出现次数最多的子树元素和（★）

2016-05-22 约 256 字预计阅读 1 分钟次阅读

力扣第 508 题

题目

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]

示例 2：

输入: root = [5,2,-5]
输出: [2]

提示:

节点数在 [1, 10⁴] 范围内
-10⁵ <= Node.val <= 10⁵

分析

统计所有的子树元素和即可。计算根节点的递归过程中就可以完成统计了。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
    def help(root):
        if not root:
            return 0
        key = root.val + help(root.left) + help(root.right)
        ct[key] += 1
        return key

    ct = Counter()
    help(root)
    M = max(ct.values())
    return [key for key in ct if ct[key] == M]

64 ms

目录

0508：出现次数最多的子树元素和（★）

题目

分析

解答