侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-19 / 0 评论 / 0 点赞 / 28 阅读 / 511 字 / 正在检测是否收录...

题目

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


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

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

示例 1:

image-20220619211110864

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

示例 2:

image-20220619211115956

输入: 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;
    }
}
0

评论区