diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /max_sum_binary_tree.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'max_sum_binary_tree.c')
-rw-r--r-- | max_sum_binary_tree.c | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/max_sum_binary_tree.c b/max_sum_binary_tree.c new file mode 100644 index 0000000..0a43dfb --- /dev/null +++ b/max_sum_binary_tree.c @@ -0,0 +1,64 @@ +// 1161. Maximum Level Sum of a Binary Tree +#include <limits.h> +#include <stdlib.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. + */ + +struct TreeNode { + int val; + struct TreeNode *left; + struct TreeNode *right; +}; + +int maxLevelSum(struct TreeNode *root) { + struct TreeNode **even = malloc(5000 * sizeof(struct TreeNode *)); + struct TreeNode **odd = malloc(5000 * sizeof(struct TreeNode *)); + int even_idx = 0, odd_idx = 0; + even[0] = root, even_idx = 1; + int max_sum = INT_MIN, max_id = -1, level = 1; + while (even_idx || odd_idx) { + int sum = 0; + if (even_idx) { + for (int i = 0; i < even_idx; i++) { + sum += even[i]->val; + if (even[i]->left) { + odd[odd_idx] = even[i]->left; + odd_idx++; + } + if (even[i]->right) { + odd[odd_idx] = even[i]->right; + odd_idx++; + } + } + if (sum > max_sum) { + max_sum = sum; + max_id = level; + } + even_idx = 0; + level++; + } else { + for (int i = 0; i < odd_idx; i++) { + sum += odd[i]->val; + if (odd[i]->left) { + even[even_idx] = odd[i]->left; + even_idx++; + } + if (odd[i]->right) { + even[even_idx] = odd[i]->right; + even_idx++; + } + } + if (sum > max_sum) { + max_sum = sum; + max_id = level; + } + odd_idx = 0; + level++; + } + } + return max_id; +} |