Medium

题目描述

给你二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同且最多，可以按 任意顺序 返回它们。

对于给定的结点，其 子树元素和 定义为以该结点为根的子树上所有结点的值之和（包括结点本身）。

示例 1：

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

示例 2：

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

提示：

  • 树中结点数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

解题思路

这道题需要我们找到二叉树中出现频率最高的子树元素和。核心思路是使用深度优先搜索（DFS）和哈希表。

解题步骤：

  1. 计算子树和：对于每个节点，其子树和等于该节点的值加上左子树和右子树的和。这可以通过后序遍历（左右根）来实现。

  2. 记录频率：使用哈希表统计每个子树和出现的次数。在递归过程中，每计算出一个子树和，就在哈希表中增加其计数。

  3. 找最大频率：遍历完整棵树后，找出哈希表中的最大频率值。

  4. 收集结果：将所有频率等于最大频率的子树和收集到结果数组中返回。

时间复杂度分析：需要遍历每个节点一次来计算子树和，然后遍历哈希表找最大频率，总体为O(n)。

空间复杂度分析：哈希表最多存储n个不同的子树和，递归调用栈深度最坏为O(n)，因此空间复杂度为O(n)。

这种方法简洁高效，一次遍历即可完成所有计算。

代码实现

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> freq;
        int maxFreq = 0;
        
        function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
            if (!node) return 0;
            
            int sum = node->val + dfs(node->left) + dfs(node->right);
            freq[sum]++;
            maxFreq = max(maxFreq, freq[sum]);
            return sum;
        };
        
        dfs(root);
        
        vector<int> result;
        for (auto& [sum, count] : freq) {
            if (count == maxFreq) {
                result.push_back(sum);
            }
        }
        
        return result;
    }
};

class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        freq = {}
        max_freq = 0
        
        def dfs(node):
            nonlocal max_freq
            if not node:
                return 0
            
            subtree_sum = node.val + dfs(node.left) + dfs(node.right)
            freq[subtree_sum] = freq.get(subtree_sum, 0) + 1
            max_freq = max(max_freq, freq[subtree_sum])
            return subtree_sum
        
        dfs(root)
        
        return [s for s, count in freq.items() if count == max_freq]

public class Solution {
    public int[] FindFrequentTreeSum(TreeNode root) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        int maxFreq = 0;
        
        int Dfs(TreeNode node) {
            if (node == null) return 0;
            
            int sum = node.val + Dfs(node.left) + Dfs(node.right);
            freq[sum] = freq.GetValueOrDefault(sum, 0) + 1;
            maxFreq = Math.Max(maxFreq, freq[sum]);
            return sum;
        }
        
        Dfs(root);
        
        List<int> result = new List<int>();
        foreach (var kvp in freq) {
            if (kvp.Value == maxFreq) {
                result.Add(kvp.Key);
            }
        }
        
        return result.ToArray();
    }
}

var findFrequentTreeSum = function(root) {
    const sumFreq = new Map();
    
    function getSum(node) {
        if (!node) return 0;
        
        const sum = node.val + getSum(node.left) + getSum(node.right);
        sumFreq.set(sum, (sumFreq.get(sum) || 0) + 1);
        return sum;
    }
    
    getSum(root);
    
    const maxFreq = Math.max(...sumFreq.values());
    return [...sumFreq.entries()]
        .filter(([sum, freq]) => freq === maxFreq)
        .map(([sum, freq]) => sum);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树的每个节点一次计算子树和，然后遍历哈希表找最大频率
空间复杂度O(n)哈希表最多存储n个不同的子树和，递归栈深度最坏情况为O(n)

相关题目