Leetcode/Problem-1161.cpp at master · VikasKumarRoy/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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Problem  - 1161
// https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/


// O(n) solution usign dfs with queue
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if(!root)
            return 0;
        queue <TreeNode* > q;
        q.push(root);
        int mx = 0;
        int ans = 0;
        int ctr = 0;
        while(!q.empty()) {
            int level = q.size();
            int sum = 0;
            ctr++;
            while(level--) {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            if(sum > mx) {
                mx = sum;
                ans = ctr;
            }
        }
        return ans;

    }
};

//another approach
class Solution {
public:

    //vector <int> levels(10000);
    int levels[10000] = {0};
    int max_level = 0;
    void findMax(TreeNode* root, int d) {
        if(!root)
            return;
        levels[d] += root->val;
        findMax(root->left, d+1);
        findMax(root->right, d+1);
        max_level = max(max_level, d);
    }

    int maxLevelSum(TreeNode* root) {
        if(!root)
            return 0;
        int ans = 0;
        int mx = 0;
        findMax(root, 1);
        vector <int> a(19);
        for(int i = 1; i <= max_level; i++) {
            if(mx < levels[i]) {
                mx = levels[i];
                ans = i;
            }
        }
        return ans;
    }
};