2024-01-30|閱讀時間 ‧ 約 0 分鐘

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

題目敘述

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

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.