首页 > 程序开发 > 软件开发 > 其他 >

leetcode 508题目解答

2017-02-23

leetcode 508题目解答:经典的树的DFS搜索,采用map操作,得到result和出现的次数的对照表格,然后利用机械的方法,得到最大次数对应的result值。

leetcode 508题目解答:经典的树的DFS搜索,采用map操作,得到result和出现的次数的对照表格,然后利用机械的方法,得到最大次数对应的result值。

在这个问题中,竟然因为
iterator的使用浪费大量时间,不值得推崇。

/**
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    map countMap;

    int sum(TreeNode * root)
    {
        if(root==NULL) 
            return 0;
        else
        {
            int result = sum(root->left)+sum(root->right)+root->val;   

            if(countMap.count(result)==0)
                countMap[result]=1;
            else
                countMap[result]++;

            return result;
        }
    }

    vector findFrequentTreeSum(TreeNode* root) {

        vector frequentNum;
        if (root==NULL)
            return frequentNum;
        else
        {
            sum(root);

            map::iterator it=countMap.begin();

            int maxFre=(it)->second;
            for(it;it!=countMap.end();it++)
            {
                if(it->second>maxFre)
                    maxFre=it->second;
            }

            for(it=countMap.begin();it!=countMap.end();it++)
            {
                if(maxFre==it->second)
                    frequentNum.push_back(it->first);
            }

            return frequentNum;
        }
    }
};
相关文章
最新文章
热点推荐