前往
大廳
主題

LeetCode - 1161. Maximum Level Sum of a Binary Tree 解題心得

Not In My Back Yard | 2024-03-11 12:00:05 | 巴幣 0 | 人氣 51

題目連結:


題目意譯:
給定一個二元樹的根節點 root,其中根節點的階層為 1、其小孩節點之階層為 2,以此類推。

回傳最小的階層 x 使得位於階層 x 的所有節點之數值總和是最大化的。

限制:
樹中的節點數量位於範圍 [1, 10 ^ 4] 中。
-10 ^ 5 ≦ Node.val ≦ 10 ^ 5



範例測資:
範例 1:
輸入: root = [1,7,0,7,-8,null,null]
輸出: 2
解釋:
階層 1 的總和 = 1。
階層 2 的總和 = 7 + 0 = 7。
階層 3 的總和 = 7 + -8 = -1。
所以我們回傳有著最大的總和之階層,而其為階層 2。

範例 2:
輸入: root = [989,null,10250,98693,-89388,null,null,null,-32127]
輸出: 2


解題思維:
單純地進行一次階層探訪(Level-Order Traversal,可以參見這題),並算出每一層各自的總和取「最早出現」(因為所求是最小的索引值)最大總和之階層即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作