【leetcode刷题】T137-出现次数最多的子树元素和

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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findFrequentTreeSum(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        self.d = {}
        self.get_sum(root)
        max_count = max(self.d.values())
        res = list(map(lambda x: x[0], filter(lambda x: x[1] == max_count, self.d.items())))
        return res

    def get_sum(self, node):
        if not node:
            return 0 
        val = node.val + self.get_sum(node.left) + self.get_sum(node.right)
        self.d[val] = self.d.get(val, 0) + 1
        return val

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        if(!root)
            return res;
        map<int, int> d;
        get_sum(root, d);

        int max_val = 0;
        map<int, int>:: iterator it;
        for(it = d.begin(); it != d.end(); it++){
            if(it->second > max_val){
                max_val = it->second;
                res.erase(res.begin(), res.end());
                res.push_back(it->first);
            }else{
                if(it->second == max_val)
                    res.push_back(it->first);
            }
        }
        return res;
    }

    int get_sum(TreeNode* node, map<int, int>& d){
        if(!node)
            return 0;
        int val = node->val + get_sum(node->left, d) + get_sum(node->right, d);
        d[val]++;
        return val;
    }
};