blob: 64d1d20e6b95b0c30cbd98d95485099ec3c7143c (
plain)
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
|
// 1161. Maximum Level Sum of a Binary Tree
#include "leetcode.h"
/*
* given the 'root' of a binary tree, the level of its root is 1, the level of
* its children is 2, and so on. return the smallest level 'x' such that the sum
* of all the values of nodes at level 'x' is maximal.
*/
class Solution {
vector<int> sums;
void dfs(TreeNode *root, size_t level) {
if (root) {
sums.resize(max(sums.size(), level));
sums[level - 1] += root->val;
dfs(root->left, level + 1);
dfs(root->right, level + 1);
}
}
public:
int maxLevelSum(TreeNode *root) {
dfs(root, 1);
return distance(begin(sums), max_element(begin(sums), end(sums))) + 1;
}
};
|