題目鏈接

給你一個二叉樹的根結點，請你找出出現(xiàn)次數(shù)最多的子樹元素和涮坐。一個結點的「子樹元素和」定義為以該結點為根的二叉樹上所有結點的元素之和（包括結點本身）凄贩。

你需要返回出現(xiàn)次數(shù)最多的子樹元素和。如果有多個元素出現(xiàn)的次數(shù)相同袱讹，返回所有出現(xiàn)次數(shù)最多的子樹元素和（不限順序）疲扎。

示例 1：

輸入:

  5
 /  \
2   -3
返回 [2, -3, 4]昵时，所有的值均只出現(xiàn)一次，以任意順序返回所有值椒丧。

示例 2：

輸入：

  5
 /  \
2   -5
返回 [2]壹甥，只有 2 出現(xiàn)兩次，-5 只出現(xiàn) 1 次壶熏。

提示：假設任意子樹元素和均可以用 32 位有符號整數(shù)表示句柠。

解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        // 1.計算所有子樹元素和(深度優(yōu)先搜索法)
        List<Integer> treeSumList = new ArrayList<>();
        getTreeSumList(root, treeSumList);
        // 2.取出數(shù)組中出現(xiàn)次數(shù)最多的元素，用map結構存儲出現(xiàn)的元素與其出現(xiàn)次數(shù)的對應關系
        Map<Integer, Integer> occurCountMap = new HashMap<>();
        for (int treeSum : treeSumList)
            occurCountMap.put(treeSum, occurCountMap.getOrDefault(treeSum, 0)+1);
        List<Integer> resultList = new ArrayList<>();
        // 統(tǒng)計出現(xiàn)次數(shù)最多的子樹元素和次數(shù)棒假，動態(tài)維護子樹元素和值
        int maxCount = 0, value;
        for (int key : occurCountMap.keySet()) {
            if ((value = occurCountMap.get(key)) > maxCount) {
                resultList.clear();
                resultList.add(key);
                maxCount = value;
            } else if (value == maxCount) {
                resultList.add(key);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = resultList.get(i);
        return result;
    }

    // 獲取root為根節(jié)點下的所有子樹元素和
    public int getTreeSumList(TreeNode root, List<Integer> treeSumList) {
        if (root == null) return 0;
        int leftTreeSum = 0, rightTreeSum = 0, treeSum;
        if (root.left != null) leftTreeSum = getTreeSumList(root.left, treeSumList);
        if (root.right != null) rightTreeSum = getTreeSumList(root.right, treeSumList);
        treeSumList.add(treeSum = leftTreeSum+rightTreeSum+root.val);
        return treeSum;
    }
}