From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- max_sum_binary_tree.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) create mode 100644 max_sum_binary_tree.cpp (limited to 'max_sum_binary_tree.cpp') diff --git a/max_sum_binary_tree.cpp b/max_sum_binary_tree.cpp new file mode 100644 index 0000000..64d1d20 --- /dev/null +++ b/max_sum_binary_tree.cpp @@ -0,0 +1,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 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; + } +}; -- cgit v1.2.3