508 出現次數最多的子樹元素和（遞歸）

1. 問題描述：

給你一個二叉樹的根結點，請你找出出現次數最多的子樹元素和。一個結點的「子樹元素和」定義為以該結點為根的二叉樹上所有結點的元素之和（包括結點本身）。

你需要傳回出現次數最多的子樹元素和。如果有多個元素出現的次數相同，傳回所有出現次數最多的子樹元素和（不限順序）。

示例 1：

輸入:

  5

 /   \

2   -3

傳回 [2, -3, 4]，所有的值均隻出現一次，以任意順序傳回所有值。

示例 2：

輸入：

  5

 /  \

2   -5

傳回 [2]，隻有 2 出現兩次，-5 隻出現 1 次。

提示： 假設任意子樹元素和均可以用 32 位有符号整數表示。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/most-frequent-subtree-sum

2. 思路分析：

① 分析題目可以知道我們可以在周遊二叉樹的時候計算目前節點下所有節點的和，在周遊的時候遞歸計算左右子樹的和加上目前根節點的值就是目前節點下所有節點的和，也即子樹元素和，我們其實是可以在遞歸的時候維護目前的子樹元素和的次數這樣就可以在遞歸的時候就可以同步更新目前的答案。可以使用哈希表dic來維護子樹元素和出現的次數，聲明int類型的變量maxC來記錄到目前為止出現的子樹元素和的最大次數，記錄答案的list類型變量res，當發現目前子樹元素和出現的次數大于了maxC，說明出現了出現了次數更大的，那麼我們就需要更新一下maxC和res，如果等于了maxC，說明出現了次數相等的子樹元素和則需要往答案中加入目前的子樹元素和s。類似于力扣之前的501題。

② 因為使用的是python語言，一開始的時候我是直接在遞歸方法中傳遞list類型的變量res來更新答案，但是後面發現如果令res = [s]是無法同步修改方法中傳遞的res變量值的，也即遞歸調用傳回到上一層的時候res變量的值是無法同步修改的，隻有往res加入元素（append），删除元素（remove），清空元素（clear）的時候才會在遞歸調用傳回到上一層的時候更新res變量，這裡可以先清空一下res的元素，然後往res中添加元素這樣在遞歸傳回到上一層的時候res是同步更新的，如果想在遞歸方法中修改res變量的值，還可以聲明全局變量這樣使用self.來通路變量那麼在遞歸調用傳回到上一層的時候也會修改res變量的值。

3. 代碼如下：

from typing import List
import collections


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    maxC = 0

    def dfs(self, root: TreeNode, res:List[int], dic: collections.defaultdict):
        if not root: return 0
        # 計算目前節點下的節點的和
        s = self.dfs(root.left, res, dic) + self.dfs(root.right, res, dic) + root.val
        dic[s] += 1
        # 出現了次數更大的說明需要更新答案
        if dic[s] > self.maxC:
            # 清空res中的所有元素, 這個操作可以修改方法中res變量的值,這樣傳回到上一層的時候res才會修改, 如果使res = [s]是無法同步修改的
            res.clear()
            # 往res中加入元素
            res.append(s)
            self.maxC = dic[s]
        elif dic[s] == self.maxC:
            res.append(s)
        return s

    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        dic = collections.defaultdict(int)
        res = list()
        self.dfs(root, res, dic)
        return res
           

聲明res為全局變量：

from typing import List
import collections


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    maxC = 0
    # 聲明全局變量
    res, dic = None, None

    def dfs(self, root: TreeNode):
        if not root: return 0
        s = self.dfs(root.left) + self.dfs(root.right) + root.val
        self.dic[s] += 1
        if self.dic[s] > self.maxC:
            self.res = [s]
            self.maxC = self.dic[s]
        elif self.dic[s] == self.maxC:
            self.res.append(s)
        return s

    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        dic = collections.defaultdict(int)
        res = list()
        self.res = res
        self.dic = dic
        self.dfs(root)
        return self.res