[LeetCode] 508. Most Frequent Subtree Sum

[grandyang]

 

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，但是绝对不是最好的方法。我们想下子树有何特点，必须是要有叶结点，单独的一个叶结点也可以当作是子树，那么子树是从下往上构建的，这种特点很适合使用后序遍历，我们使用一个 HashMap 来建立子树和跟其出现频率的映射，用一个变量 cnt 来记录当前最多的次数，递归函数返回的是以当前结点为根结点的子树结点值之和，然后在递归函数中，我们先对当前结点的左右子结点调用递归函数，然后加上当前结点值，然后更新对应的 HashMap 中的值，然后看此时 HashMap 中的值是否大于等于 cnt，大于的话首先要清空 res，等于的话不用，然后将 sum 值加入结果 res 中即可，参见代码如下：

 

解法一：

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int cnt = 0;
        postorder(root, m, cnt, res);
        return res;
    }
    int postorder(TreeNode* node, unordered_map<int, int>& m, int& cnt, vector<int>& 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<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> 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<int, int>& 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;
    }
};

 

开始我还在想能不能利用后序遍历的迭代形式来解，后来想了半天发现不太容易实现，因为博主无法想出有效的机制来保存左子树结点之和，而计算完对应的右子树结点之和后要用到对应的左子树结点之和，才能继续往上算。可能博主不够 smart，有大神如果知道如何用迭代的形式来解，请一定要留言告知博主啊，多谢啦～

 

Github 同步地址：

#508

 

类似题目：

Subtree of Another Tree

 

参考资料：

https://leetcode.com/problems/most-frequent-subtree-sum/

https://leetcode.com/problems/most-frequent-subtree-sum/discuss/98675/JavaC%2B%2BPython-DFS-Find-Subtree-Sum

https://leetcode.com/problems/most-frequent-subtree-sum/discuss/98664/Verbose-Java-solution-postOrder-traverse-HashMap-(18ms)

 

LeetCode All in One 题目讲解汇总(持续更新中...)