一題多解: 二元樹裡，最大Level sum是在哪一層? Leetcdoe #1161

Gabriel Sollmann on Unsplash

題目敘述

題目會給我們一棵二元樹的根結點，要求我們找出哪一層擁有最大的水平元素和(Level-sum)?

題目的原文敘述

測試範例

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

節點總樹目介於1~10^4之間。

• -10^5 <= Node.val <= 10^5

節點值都介於 負十萬 ~ 正十萬 之間。

演算法 BFS

解題線索就在題目裡了！

題目已經問： 哪一層有最大的水平元素和?

那很自然就會想到用擁有逐層由內往外探索的BFS廣度優先搜尋囉！

每一層各自累加元素總合，紀錄擁有最大值的那個level即可。

程式碼 BFS

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:

        bfs_queue = deque([(root,1)])

        max_sum, max_level = -math.inf, -1

        
        # BFS traversal, level by level
        while bfs_queue:
            
            cur_sum = 0 
            for _ in range( len(bfs_queue) ):

                node, level = bfs_queue.popleft()
                cur_sum += node.val

                if node.left: bfs_queue.append( (node.left, level+1) )
                if node.right: bfs_queue.append( (node.right, level+1) )

            # update the level with max level sum
            if cur_sum > max_sum:
                max_sum = cur_sum
                max_level = level

        return max_level

複雜度分析 討論可能的情況，並且分類。
使用DFS深度優先搜索

時間複雜度:

從根結點開始，探索整顆樹，每個結點最多拜訪一次，所需時間為O(n)。