LeetCode508. 出现次数最多的子树元素和

题目描述

本题目来自LeetCode上的『508. 出现次数最多的子树元素和』

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

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

示例1：

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

提示

• 节点数在 [1, 104] 范围内
• -10^5 <= Node.val <= 10^5

题解

题意就是让我们求出树中每个子树的和，然后返回出现次数最多的和。
深搜求每个子树和，使用一个哈希表记录每个子树和出现的次数，遍历哈希表找到次数最大的几个子树和。

代码

class Solution {
private:
    unordered_map<int, int> mp;
    int dfs(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int ret = root->val;
        ret += dfs(root->left) + dfs(root->right);
        ++mp[ret];
        return ret;
    }
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> ans;
        dfs(root);
        int maxCnt = 0;
        for (const auto& [_, cnt]: mp) {
            maxCnt = max(cnt, maxCnt);
        }
        for (const auto& [sum, cnt]: mp) {
            if (cnt == maxCnt) {
                ans.emplace_back(sum);
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n)$，$n$ 为结点个数。
• 空间复杂度：$O(n)$。