leetcode/Problems/0508.cpp at master · DimitrijeDobrota/leetcode · GitHub

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
class Solution {
  public:
    vector<int> findFrequentTreeSum(TreeNode *root) {
        unordered_map<int, int> um;
        stack<TreeNode *> st({root});
        while (!st.empty()) {
            TreeNode *root = st.top();
            if (root) {
                st.push(nullptr);
                if (root->left) st.push(root->left);
                if (root->right) st.push(root->right);
                continue;
            }
            st.pop();
            root = st.top();
            st.pop();
            if (root->left) root->val += root->left->val;
            if (root->right) root->val += root->right->val;
            um[root->val]++;
        }

        vector<int> res;
        int maxi = 0;
        for (const auto [k, v] : um) {
            if (v < maxi) continue;
            if (v == maxi)
                res.push_back(k);
            else {
                maxi = v;
                res = {k};
            }
        }
        return res;
    }
};