[LeetCode] Most Frequent Subtree Sum 出现频率最高的子树和-白红宇

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1

Input:

5 /  \2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2

Input:

5 /  \2   -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

这道题给了我们一个二叉树，让我们求出现频率最高的子树之和，求树的结点和并不是很难，就是遍历所有结点累加起来即可。那么这道题的暴力解法就是遍历每个结点，对于每个结点都看作子树的根结点，然后再遍历子树所有结点求和，这样也许可以通过OJ，但是绝对不是最好的方法。我们想下子树有何特点，必须是要有叶结点，单独的一个叶结点也可以当作是子树，那么子树是从下往上构建的，这种特点很适合使用后序遍历，我们使用一个哈希表来建立子树和跟其出现频率的映射，用一个变量cnt来记录当前最多的次数，递归函数返回的是以当前结点为根结点的子树结点值之和，然后在递归函数中，我们先对当前结点的左右子结点调用递归函数，然后加上当前结点值，然后更新对应的哈希表中的值，然后看此时哈希表中的值是否大于等于cnt，大于的话首先要清空res，等于的话不用，然后将sum值加入结果res中即可，参见代码如下：

解法一：

class Solution {public:    vector
      
        findFrequentTreeSum(TreeNode* root) {        vector
       
         res;        unordered_map
        
          m;        int cnt = 0;        postorder(root, m, cnt, res);        return res;    }    int postorder(TreeNode* node, unordered_map
         
          & m, int& cnt, vector
          
           & res) {        if (!node) return 0;        int left = postorder(node->left, m, cnt, res);        int right = postorder(node->right, m, cnt, res);        int sum = left + right + node->val;        ++m[sum];        if (m[sum] >= cnt) {            if (m[sum] > cnt) res.clear();            res.push_back(sum);            cnt = m[sum];        }        return sum;    }};

下面这种解法跟上面的基本一样，就是没有在递归函数中更新结果res，更是利用cnt，最后再更新res，这样做能略微高效一些，参见代码如下：

解法二：

class Solution {public:    vector
      
        findFrequentTreeSum(TreeNode* root) {        vector
       
         res;        unordered_map
        
          m;        int cnt = 0;        postorder(root, m, cnt);        for (auto a : m) {            if (a.second == cnt) res.push_back(a.first);        }        return res;    }    int postorder(TreeNode* node, unordered_map
         
          & m, int& cnt) {        if (!node) return 0;        int left = postorder(node->left, m, cnt);        int right = postorder(node->right, m, cnt);        int sum = left + right + node->val;        cnt = max(cnt, ++m[sum]);        return sum;    }};

本文转自博客园Grandyang的博客，原文链接：，如需转载请自行联系原博主。