[Leetcode] 1161. Maximum Level Sum of a Binary Tree

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/

initial

I solved it via dfs and adding values to the respective levels. But i only beat 20% of submissions. BFS is more time efficient

dfs way

from collections import defaultdict
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return None
        dic = defaultdict(int)

        def dfs(root,level):
            if not root:
                return
            dic[level]+=root.val
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        dfs(root,1)
        ansVal=-int(10e18)
        ansLevel=0
        # print(dic)
        # print(sorted(dic.items(),key=lambda x:x[0]))
        for key,val in dic.items():
            if val>ansVal:
                ansVal=val
                ansLevel=key
        return ansLevel

bfs way

def maxLevelSum(root: TreeNode) -> int:
    """
    Finds the level in a binary tree with the maximum sum of node values.

    Args:
        root: The root node of the binary tree.

    Returns:
        The level number with the maximum sum, or 0 if the tree is empty.
    """
    if not root:
        return 0

    queue = [root]
    max_sum = float('-inf')
    max_level = 1
    level = 1

    while queue:
        level_sum = 0
        level_size = len(queue)

        for _ in range(level_size):
            node = queue.pop(0)
            level_sum += node.val

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

        if level_sum > max_sum:
            max_sum = level_sum
            max_level = level

        level += 1

    return max_level

complexity

Both BFS and DFS have a time complexity of O(N).
BFS has a space complexity of O(W), which can be O(N) in the worst case.
DFS has a space complexity of O(H), which can be O(N) in the worst case (skewed tree) and O(log(N)) in the best case (balanced tree).