前往
大廳
主題

LeetCode - 2583. Kth Largest Sum in a Binary Tree 解題心得

Not In My Back Yard | 2024-02-07 12:00:01 | 巴幣 1000 | 人氣 58

題目連結:


題目意譯:
你被給定一棵二元樹的根節點 root 以及一個正整數 k。

樹中的階層和為同一階層上所有節點值之總和。

回傳樹中第 k 大的階層和(總和值不一定彼此相異)。如果樹中少於 k 個階層,則回傳 -1。

注意到兩個節點衛位於同一階層,代表著它們距離根節點是一樣的。

限制:
樹中的節點數為 n。
2 ≦ n ≦ 10 ^ 5
1 ≦ Node.val ≦ 10 ^ 6
1 ≦ k ≦ n



範例測資:
範例 1:
輸入: root = [5,8,9,2,1,3,7,4,6], k = 2
輸出: 13
解釋: 各個階層和為以下:
- 階層 1: 5。
- 階層 2: 8 + 9 = 17。
- 階層 3: 2 + 1 + 3 + 7 = 13。
- 階層 4: 4 + 6 = 10。
第 2 大的階層和為 13。

範例 2:
輸入: root = [1,2,null,3], k = 1
輸出: 3
解釋: 最大的階層和為 3。


解題思維:
就是單純地進行一次階層探訪(參見這題)並算出每一層的總和並排序得到第 k 大即可。當然,如果階層不足 k 層則直接回傳 -1。




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

創作回應

更多創作