时间Vs杀手

LeetCode--508. 出现次数最多的子树元素和
给出二叉树的根,找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和(...
扫描右侧二维码阅读全文
04
2018/12

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

给出二叉树的根,找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的元素(不限顺序)。

示例 1
输入:

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

示例 2
输入:

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

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

思路:递归求解就行了

/**
 * 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==NULL)return res;
        map<int,int> mm;
        int sum = fuc(root,mm);
        
        int max_key = 0;
        int max_value = INT_MIN;
        for(map<int,int>::iterator it=mm.begin();it!=mm.end();it++){
            int key = it->first;
            int val = it->second;
            if(val>max_value){
                max_key = key;
                max_value = val;
            }
        }
        
        
        for(map<int,int>::iterator it=mm.begin();it!=mm.end();it++){
            int key = it->first;
            int val = it->second;
            if(val==max_value){
                res.push_back(key);
            }
        }
        return res;
        
    }
    
    int fuc(TreeNode* root,map<int,int> &mm){
        if(root->left==NULL&&root->right==NULL){
            int num = root->val;
            if(mm.find(num)!=mm.end()){
                mm[num]+=1;
            }else{
                mm[num] = 1;
            }
            return num;
        }
        
        int sum = root->val + (root->left==NULL?0:fuc(root->left,mm)) + (root->right==NULL?0:fuc(root->right,mm));
        if(mm.find(sum)!=mm.end()){
            mm[sum]+=1;
        }else{
            mm[sum] = 1;
        }
        return sum;
    }
};
Last modification:December 4th, 2018 at 09:20 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment