508 出现次数最多的子树元素和（递归）

太过爱你忘了你带给我的痛 2022-08-30 00:46 116阅读 0赞

**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

[501]: https://blog.csdn.net/qq_39445165/article/details/118830793