How to Find out the Most Frequent Subtree Sum using Depth First

  • 时间:2020-09-25 11:32:47
  • 分类:网络文摘
  • 阅读:87 次

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.

Most Frequent Subtree Sum using DFS Algorithm

We can use a hash map e.g. unordered_map in C++ to store the Subtree sum and their frequencies. Also, we need to keep track of the maximum frequency so that later we can iterate the map and push the sum (that is one of the most occurred) to the result.

We need to search the entire binary tree using Depth First Search algorithm, in recursion style.

The frequencies of the current subtree sum are updated before recursion calls.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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) {
        dfs(root);
        vector<int> r;
        for (auto it = sums.begin(); it != sums.end(); ++ it) {
            if (it->second == count) { // check if it is one of the max occurred number
                r.push_back(it->first);
            }
        }
        return r;
    }
    
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftsum = dfs(root->left);
        int rightsum = dfs(root->right);
        int sum = root->val + leftsum + rightsum;
        if (sums.find(sum) == sums.end()) {
            sums[sum] = 1;
        } else {
            sums[sum] ++;
        }
        count = max(count, sums[sum]); // update max freq
        return sum;
    }
    
private:
    // sum and the frequencies 
    unordered_map<int, int> sums;
    // max frequency
    int count = 0;
};
/**
 * 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) {
        dfs(root);
        vector<int> r;
        for (auto it = sums.begin(); it != sums.end(); ++ it) {
            if (it->second == count) { // check if it is one of the max occurred number
                r.push_back(it->first);
            }
        }
        return r;
    }
    
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftsum = dfs(root->left);
        int rightsum = dfs(root->right);
        int sum = root->val + leftsum + rightsum;
        if (sums.find(sum) == sums.end()) {
            sums[sum] = 1;
        } else {
            sums[sum] ++;
        }
        count = max(count, sums[sum]); // update max freq
        return sum;
    }
    
private:
    // sum and the frequencies 
    unordered_map<int, int> sums;
    // max frequency
    int count = 0;
};

The runtime complexity for the above C++ DFS algorithm is O(N) where N is the number of the nodes in the binary tree i.e. each node has to be visited exactly once. And the space complexity is O(N) because a binary tree with N nodes will have N subtrees exactly and we are using a hashmap to store those sum values.

With C++ unordered_map, the default value (when it is integer) is zero, thus we can simply do this instead to update the counter:

1
sums[sum] ++;
sums[sum] ++;

The same DFS algorithm can be applied to solve this: The Maximum Average Subtree of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
那一次,我真尴尬  我和祖国同生日  静湖公园作文  《青铜葵花》有感300字  儿童的负重最好不要超过体重的20分之3  仓库先后运来两批粮食,如果只有第一批增加20%  小东的爷爷积攒了5000元钱打算存入银行  绿地长24米,宽15米,中间有宽为2米的道路  一群兔子在一块地里拔萝卜  学校组织春游,组了几条船让学生们划 
评论列表
添加评论