【二叉树, DFS, 哈希表】出现次数最多的子树元素和

题目

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

---

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

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

示例 1：

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

示例 2：

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

提示:

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

解题

方法一：DFS 哈希表

思路

使用 DFS 对树进行遍历，同时将每棵子树的总和值存入哈希表(map)（键为元素和，值为出现次数），并实时维护最大子树和，使用变量 max 存储。

当遍历完整棵树后，将哈希表中值为 max 的键存入答案。

代码

class Solution {
    private Map<Integer, Integer> map;
    private int max;

    public int[] findFrequentTreeSum(TreeNode root) {
        map = new HashMap<>();
        dfs(root);
        List<Integer> counts = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == max) counts.add(entry.getKey());
        }
        int[] ans = new int[counts.size()];
        for (int i = 0; i < counts.size(); i++) ans[i] = counts.get(i);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int sum = node.val + dfs(node.left) + dfs(node.right);
        int count = map.getOrDefault(sum, 0) + 1;
        if (count > max) max = count;
        map.put(sum, count);
        return sum;
    }
}

优化

在 DFS 的过程中维护最大子树和集合。

class Solution {
    private Map<Integer, Integer> map;
    private List<Integer> list;
    private int max;

    public int[] findFrequentTreeSum(TreeNode root) {
        map = new HashMap<>();
        list = new ArrayList<>();
        dfs(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) ans[i] = list.get(i);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int sum = node.val + dfs(node.left) + dfs(node.right);
        int count = map.getOrDefault(sum, 0) + 1;
        if (count == max) list.add(sum);
        else if (count > max) {
            list.clear();
            list.add(sum);
            max = count;
        }
        map.put(sum, count);
        return sum;
    }
}