Problem of The Day: Maximum Level Sum of a Binary Tree

Problem Statement

leetcode problem link

My Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxLevelSum(TreeNode root) {
        int res = 0;
        int currMax = int.MinValue;
        int level = 0;
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            var n = queue.Count;
            var curr = 0;
            level += 1;
            for (var i = 0; i < n; i++) {
                var node = queue.Dequeue();
                curr += node.val;
                if (node.left is not null) {
                    queue.Enqueue(node.left);
                }
                if (node.right is not null) {
                    queue.Enqueue(node.right);
                }
            }
            if (curr > currMax) {
                currMax = curr;
                res = level;
            }
        }
        return res;
    }
}

Editorial

Approach 1: Breadth First Search

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        max_sum, ans, level = float('-inf'), 0, 0

        q = collections.deque()
        q.append(root)

        while q:
            level += 1
            sum_at_current_level = 0
            # Iterate over all the nodes in the current level.
            for _ in range(len(q)):
                node = q.popleft()
                sum_at_current_level += node.val

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            if max_sum < sum_at_current_level:
                max_sum, ans = sum_at_current_level, level

        return ans

Approach 2: Depth First Search

class Solution:
    def dfs(
        self, node: Optional[TreeNode], level: int, sum_of_nodes_at_level: List[int]
    ) -> None:
        if node is None:
            return

        if len(sum_of_nodes_at_level) == level:
            sum_of_nodes_at_level.append(node.val)
        else:
            sum_of_nodes_at_level[level] += node.val

        self.dfs(node.left, level + 1, sum_of_nodes_at_level)
        self.dfs(node.right, level + 1, sum_of_nodes_at_level)

    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        sum_of_nodes_at_level = []
        self.dfs(root, 0, sum_of_nodes_at_level)

        max_sum = float("-inf")
        ans = 0

        for i in range(len(sum_of_nodes_at_level)):
            if max_sum < sum_of_nodes_at_level[i]:
                max_sum = sum_of_nodes_at_level[i]
                ans = i + 1

        return ans