aboutsummaryrefslogtreecommitdiff
path: root/max_sum_binary_tree.cpp
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;
  }
};