LeetCode //C - 1161. Maximum Level Sum of a Binary Tree

1161. Maximum Level Sum of a Binary Tree

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.
?

Example 1:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
**Explanation: **
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

• The number of nodes in the tree is in the range $[1,10^4]$.
• $?10^5<=Node.val<=10^5$

From: LeetCode
Link: 1161. Maximum Level Sum of a Binary Tree

---

Solution:

Ideas：

1. Initial Setup:

• A dynamic queue is created to keep track of nodes to visit next. This queue will store pointers to each node in the binary tree.
• The variables maxSum and maxLevel are initialized to store the maximum sum encountered and the corresponding level number. Initially, maxSum is set to the value of the root node, and maxLevel is set to 1.

2. Enqueue Root Node:

• The root node is enqueued followed by a NULL marker. This NULL marker is used to identify when all nodes at a particular level have been processed, and it’s time to move to the next level.

3. Traversal Loop:

• The loop continues until there are no more nodes left to process in the queue.
• It dequeues nodes one by one and sums their values.
• When a NULL marker is dequeued, it means the end of the current level is reached:
  • If the sum of the current level is greater than maxSum, update maxSum and maxLevel with the current sum and level number.
  • Reset the currentSum to zero for the next level’s sum.
  • Increment the level count, and if there are more nodes to process, enqueue another NULL marker to indicate the end of the next level.

4. Child Nodes:

• For each non-NULL node dequeued, the function enqueues its child nodes (left and then right) if they exist.
• The queue size is checked and dynamically expanded if necessary by using realloc.

5. Return Maximum Level:

• After the traversal is complete, the function returns the maxLevel, which corresponds to the level with the maximum sum.

6. Memory Management:

• Before exiting the function, the dynamically allocated memory for the queue is freed to prevent memory leaks.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxLevelSum(struct TreeNode* root) {
    if (root == NULL) return 1;

    // Dynamically allocate a queue to hold pointers to TreeNodes
    int queueSize = 1024; // initial size
    struct TreeNode** queue = (struct TreeNode**)malloc(queueSize * sizeof(struct TreeNode*));
    if (!queue) return -1; // allocation failed

    int front = 0, rear = 0, level = 1, maxSum = root->val, maxLevel = 1, currentSum = 0;

    // Enqueue the root and a NULL marker for level 1
    queue[rear++] = root;
    queue[rear++] = NULL;

    while (front < rear) {
        struct TreeNode* node = queue[front++];

        if (node == NULL) {
            if (currentSum > maxSum) {
                maxSum = currentSum;
                maxLevel = level;
            }
            // Reset current sum for next level
            currentSum = 0;
            // Increase level number
            level++;
            // Continue only if there are more nodes to process
            if (front < rear) {
                queue[rear++] = NULL; // Marker for the next level
            }
        } else {
            // Add the node's value to the current level sum
            currentSum += node->val;

            // Enqueue child nodes
            if (node->left) {
                if (rear >= queueSize) {
                    // Increase queue size
                    queueSize *= 2;
                    queue = (struct TreeNode**)realloc(queue, queueSize * sizeof(struct TreeNode*));
                    if (!queue) return -1; // reallocation failed
                }
                queue[rear++] = node->left;
            }
            if (node->right) {
                if (rear >= queueSize) {
                    // Increase queue size
                    queueSize *= 2;
                    queue = (struct TreeNode**)realloc(queue, queueSize * sizeof(struct TreeNode*));
                    if (!queue) return -1; // reallocation failed
                }
                queue[rear++] = node->right;
            }
        }
    }

    free(queue); // Free the queue
    return maxLevel;
}