小鲸鱼的梦境
0%

『LeetCode』508 出现次数最多的子树元素和

发表于 分类于 Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目

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

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

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

示例 1：

freq1-tree.jpg

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

示例 2：

freq2-tree.jpg

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

提示:

  • 节点数在 \([1, 10^{4}]\) 范围内
  • \(-10^{5} <= Node.val <= 10^{5}\)

标签

树, 深度优先搜索, 哈希表, 二叉树

相似题目

题解

【出现次数最多的子树元素和】二叉树遍历&哈希表计数

模拟

按照题目要求，遍历二叉树并使用哈希表统计各个子树的元素和即可。

较简单的实现方法是常规的后序递归，函数返回值为子树的元素和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Code language: Python
class Solution:
    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        cnt = Counter()

        def dfs(root):
            if root:
                s = root.val + dfs(root.left) + dfs(root.right)
                cnt[s] += 1
                return s
            else:
                return 0
        
        dfs(root)
        val = max(cnt.values())
        return [k for k, v in cnt.items() if v == val]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Code language: Java
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> st = new HashMap<>();
        dfs(root, st);
        int cnt = 0, maxVal = Integer.MIN_VALUE;
        for (int v : st.values()) {
            if (v == maxVal)
                ++cnt;
            else if (v > maxVal) {
                maxVal = v;
                cnt = 1;
            }
        }
        int[] ans = new int[cnt];
        cnt = 0;
        for (int k : st.keySet()) {
            if (st.get(k) == maxVal)
                ans[cnt++] = k;
        }
        return ans;
    }

    public int dfs(TreeNode root, Map<Integer, Integer> st) {
        if (root == null)
            return 0;
        int cnt = root.val + dfs(root.left, st) + dfs(root.right, st);
        st.put(cnt, st.getOrDefault(cnt, 0) + 1);
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Code language: C++
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode *root) {
        int maxVal = INT32_MIN;
        unordered_map<int, int> st;
        function<int(TreeNode *)> dfs = [&st, &dfs, &maxVal](TreeNode *root) {
            if (root == nullptr) return 0;
            int cnt = root->val + dfs(root->left) + dfs(root->right);
            st[cnt]++;
            maxVal = max(maxVal, st[cnt]);
            return cnt;
        };
        dfs(root);
        vector<int> ans;
        for (auto &kv : st) {
            if (kv.second == maxVal) ans.emplace_back(kv.first);
        }
        return ans;
    }
};
  • 时间复杂度: \(O(n)\), \(n\) 为二叉树中的结点数量
  • 空间复杂度: \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~