跳转至

LeetCode: 508. 出现次数最多的子树元素和

1、题目描述

给出二叉树的根,找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的元素(不限顺序)。

示例 1

输入:

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

示例 2

输入:

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

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

2、解题思路

  • 使用dfs遍历书,同时将子树之和放入字典中
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict


class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> [int]:
        if not root:
            return []

        max_num = 0
        sums = defaultdict(int)

        def dfs(node: TreeNode):
            nonlocal max_num, sums
            if not node:
                return 0
            temp = node.val + dfs(node.left) + dfs(node.right)
            sums[temp] += 1
            max_num = max(max_num, sums[temp])
            return temp

        dfs(root)
        return [x[0] for x in sums.items() if x[1] == max_num]