1161. Maximum Level Sum of a Binary Tree

01//BFS
02//Runtime: 248 ms, faster than 15.14% of C++ online submissions for Maximum Level Sum of a Binary Tree.
03//Memory Usage: 74.3 MB, less than 100.00% of C++ online submissions for Maximum Level Sum of a Binary Tree.
04
05/**
06 * Definition for a binary tree node.
07 * struct TreeNode {
08 *     int val;
09 *     TreeNode *left;
10 *     TreeNode *right;
11 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 * };
13 */
14class Solution {
15public:
16    int maxLevelSum(TreeNode* root) {
17        queue<TreeNode*> qNode;
18        queue<int> qLevel;
19        int maxLevel = 0, maxSum = INT_MIN;
20        int lastLevel = 1, lastSum = 0;
21        TreeNode* node;
22        
23        qNode.push(root);
24        qLevel.push(lastLevel);
25        
26        while(!qNode.empty()){
27            node = qNode.front();
28            // cout << node->val << endl;
29            qNode.pop();
30            
31            lastLevel = qLevel.front();
32            qLevel.pop();
33            
34            lastSum += node->val;
35            
36            if(node->left){
37                qNode.push(node->left);
38                qLevel.push(lastLevel+1);
39            }
40            
41            if(node->right){
42                qNode.push(node->right);
43                qLevel.push(lastLevel+1);
44            }
45            
46            //clean up before entering new level
47            if(lastLevel != qLevel.front()){
48                if(lastSum > maxSum){
49                    maxSum = lastSum;
50                    maxLevel = lastLevel;
51                }
52                lastSum = 0;
53            }
54        }
55        
56        return maxLevel;
57    }
58};
59
60
61//BFS, cleaner
62//Runtime: 232 ms, faster than 55.42% of C++ online submissions for Maximum Level Sum of a Binary Tree.
63//Memory Usage: 72.7 MB, less than 100.00% of C++ online submissions for Maximum Level Sum of a Binary Tree.
64//https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360968/JavaPython-3-Two-codes-language%3A-BFS-level-traversal-and-DFS-level-sum.
65
66/**
67 * Definition for a binary tree node.
68 * struct TreeNode {
69 *     int val;
70 *     TreeNode *left;
71 *     TreeNode *right;
72 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
73 * };
74 */
75class Solution {
76public:
77    int maxLevelSum(TreeNode* root) {
78        queue<TreeNode*> q;
79        TreeNode* node;
80        int levelSize;
81        int curLevel = 1;
82        int maxSum = INT_MIN, maxLevel = -1;
83        int levelSum = 0;
84        
85        q.push(root);
86        
87        while(!q.empty()){
88            levelSize = q.size();
89            for(int i = 0; i < levelSize; i++){
90                node = q.front();
91                q.pop();
92                
93                if(node->left){
94                    q.push(node->left);
95                }
96                
97                if(node->right){
98                    q.push(node->right);
99                }
100                
101                levelSum += node->val;
102            }
103            
104            //clean up before going to next level
105            if(levelSum > maxSum){
106                maxSum = levelSum;
107                maxLevel = curLevel;
108            }
109            levelSum = 0;  
110            curLevel++;
111        }
112        
113        return maxLevel;
114    }
115};
116
117//DFS
118//https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360968/JavaPython-3-Two-codes-language%3A-BFS-level-traversal-and-DFS-level-sum.
119//Runtime: 220 ms, faster than 87.98% of C++ online submissions for Maximum Level Sum of a Binary Tree.
120//Memory Usage: 70.4 MB, less than 100.00% of C++ online submissions for Maximum Level Sum of a Binary Tree.
121/**
122 * Definition for a binary tree node.
123 * struct TreeNode {
124 *     int val;
125 *     TreeNode *left;
126 *     TreeNode *right;
127 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
128 * };
129 */
130class Solution {
131public:
132    //iterate tree and fill levelSums
133    void dfs(TreeNode* node, vector<int>& levelSums, int level){
134        if(!node) return;
135        //ex: levelSums is empty, we need to make its length 1 so that we can set levelSums[0] as node->val
136        if(level == levelSums.size()){
137            levelSums.push_back(node->val);
138        }else{
139            levelSums[level] += node->val;
140        }
141        
142        if(node->left){
143            dfs(node->left, levelSums, level+1);
144        }
145        if(node->right){
146            dfs(node->right, levelSums, level+1);
147        }
148    };
149    
150    int maxLevelSum(TreeNode* root) {
151        //levelSums[0]: the sum of nodes' values in level 0+1=1
152        vector<int> levelSums;
153
154        //pretend the first level is level 0
155        //later will add 1 to convert it to the real level
156        dfs(root, levelSums, 0);
157        
158        //max_element: Returns an iterator pointing to the element with the largest value in the range [first,last).
159        return distance(levelSums.begin(), 
160                max_element(levelSums.begin(), levelSums.end())) + 1;
161    }
162};