1161. Maximum Level Sum of a Binary Tree - chasel2361/leetcode GitHub Wiki

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: [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.

這題要求找到節點值總和最大的層數

要解決這個問題可以利用 quene 先進先出的資料型態來達到逐層搜尋的效果。

先把根結點放入 quene 中，進行與層中節點個數相同次數的迴圈，其中計算層中節點值之總和，並檢查是否有左右子樹，有則將子樹節點放入 quene。迴圈結束後檢查是否需要更新最大總和及輸出值，無則進行下一層的迴圈，程式碼如下

from collections import deque
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        """
        Arg:
            maxsum(int): maximum summation of level for now
            res(int): the level of maximum summation
            level(int): processing level
            q(quene): quene record a level of nodes
            total(int): summation of level
            cnt(int): count of nodes of level
        """
        maxsum = 0
        res = 0
        level = 1
        
        q = deque()
        q.append(root)
        
        while q:
            cnt = len(q)
            total = 0
            
            # 處理每層節點
            while cnt > 0:
                node = q.popleft()
                total += node.val
                
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                cnt -= 1
            
            if total > maxsum:
                maxsum = total
                res = level
                
            level += 1
        return res

這樣寫的時間複雜度是O(N)，空間複雜度也是O(N)