题目描述

给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

样例

示例 1：
输入:

  5
 /  \
2   -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2：
输入：

  5
 /  \
2   -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。

 

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

算法

(Hash+DFS)

这么想，要求出本题的结果，就要计算各个节点左子树累加和次数 + 左子树累加和次数 + 本节点累加次数。
所以这么一看，感觉就是用后续遍历能做的题目了。

1. 使用DFS统计必须经过root点的最大值,包括左右子树的节点和， 把出现的节点和放在一个map里面统计次数。
2. 在dfs函数中，每层dfs计算一个节点累加和对应的最大出现次数maxCnt。
3. 最后循环map，每次得到和maxCnt一样出现次数的元素加入结果集合里面。

时间复杂度 O(n)

Java 代码

class Solution {
    Map<Integer/**包括当前root节点和左右子数的和**/, Integer/**个数**/> map = new HashMap<>();

    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[] {};
        }

        int[] maxCnt = {0};    // 相同节点和出现的最大次数
        // 算路径和
        int currentSum = dfs(root, maxCnt);

        List<Integer> list = new ArrayList<>();
        map.forEach((k, v) -> {
            if (v == maxCnt[0]) {
                list.add(k);
            }
        });

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    // 返回必须经过root点的最大值,包括左右子树
    private int dfs(TreeNode root, int[] maxCnt) {
        if (root == null) {
            return 0;
        }

        int left = dfs(root.left, maxCnt);
        int right = dfs(root.right, maxCnt);
        // 包括当前root节点
        int currentSum = left + right + root.val;

        map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
        maxCnt[0] = Math.max(maxCnt[0], map.getOrDefault(currentSum, 0));
        return currentSum;
    }
}