題目敘述
題目會給我們一棵二元樹的根結點，要求我們找出哪一層擁有最大的水平元素和(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)。
