C++ Python DFS與nth element( nlargest)Leetcode 2583 Kth Largest Sum in a Binary Tree

好 各位好 我們來解今天Leap Code的問題
今天的問題是
2583題 所謂的
Cat largest sum in a binary tree
所以這個又是一個二元數的一個問題
那基本上呢 它就是給你一個二元數
那變數名稱就叫做root
那而且再給你一個正整數
所以它這邊要考慮的是所謂的level sum
就是你那個二元數呢
它每個level都有
那些節點都有它的一個值
將它合起來同一個level的level sum
在相同的level的
那些值的合就叫level sum
那請你返回
dk大的level sum
它這邊特別強調它不一定是
不相同的
它有可能有重複的level sum
基本上就是dk個
如果說你
這一顆二元數它的level如果是小於k的話
這個當然是有可能的
在這種情況下
那你要傳回去的值就是負1
它這邊特別解釋
兩個節點它是在相同的level
它會有相同的距離
到所謂的root節點
那這個是一個二元數的一個問題
好 那我們就看它的一些例子
好 那我們看它這裡的例子
它有兩個例子
第一個例子當然我們就分別一層一層去算它的level sum
第0層當然是5
第1層當然就是17
再來
第2層2加1加3加7
所以這個是13
再來這個
最後一層
當然就是4加6
當然這裡就是10
那它的k值是2
所以是第2大
第2大當然就是這裡
最大當然是17
所以這個沒有問題
這原則上就是一層一層的
把它的level sum把它算出來
然後再去dk個
dk大的
好 那我們再看第2個
第2個的話它這邊的話
k是等於1
所以最大
最大因為它每一層只有一個節點
所以最大當然就是3
我們看一下它的constraint
這跟我們的解題方式當然會有關聯
n是介於2到10萬之間
所以n可以
10的5次方
那節點的值的數字最大可以到100萬
那k呢
當然是要小於等於n
好
那我們看一下我們帶來解題的一個
技巧
好 解題的方式呢
我們其實
我們這邊考慮比較簡單實作的
所謂用DFS的方式
實際上來講它也就是所謂的
prefix order的transversal
那這個特別對二元數來講
它真的是常用的一種走法的方式
那採用DFS的方式來講的話
你就可以用遞回去寫
讓程式變得比較簡潔
所以我們就去
定義一個遞回函數
假設叫f
那基本上它就去算那個level sum
那當然它的走法當然不是所謂的
level wise的transversal
但是原則上它可以
逐次的將
節點的
的數字加到它適合的那個
level的部分
好
然後這個算完之後原則上呢
我們在它主要的這個
method裡面呢
我們去
就去宣告所謂的long long
基本上你可以用vector
或者是用一般的正例
如果是python的話
當然用一般的list就可以
那根據我們
實際實作的一個情況
最好這個
vector或者array
一次就將記憶體空間就整個配置給它
所以你可能一開始就給它配置
十六五次方
不要逐一的去
push back
逐一的push back它的速度就會緩慢
然後我們就去呼叫
我們的
遞回函數
那
當你的k呢如果是大於它的
數高
那這個時候我們根據提議當然就
返回值是-1
其他情況我們在
作用所謂的nth element
這個在C++
STD裡面的當中的一個函數
這個也蠻好用的
我們就可以找到dk大的元素
那當然在這裡的話
當然是用order是用greater
那基本上
在
sum
在k-1這個index的值就是它的答案
這個當然是C++的一個解法
那我們就實際看一下
我們在立code實作的一個情況
好那我們先看有關python版的一個做法
python版呢跟剛剛
所說明的其實也差異不大
那雖然我們在這邊的話
當然我們的list
我們是一開始就先將空間的配置給它
不要逐一的
將它append或怎樣就會緩慢
然後我們這邊的
SZ就是它的size
所以我們這裡是11行到17行的地方
我們就
定義我們的DFS
我們就採用DFS的方式去走訪
那
如果你那的節點呢如果是空的話
那當然就return回去
如果說我們的剛好我們的level呢
是大於等於SZ
我們當然就是我們SZ就要加等於1
然後我們將
root的值加到
它所在level的這個sum
好
那然後我們再考慮它的
左數
那當然這時候level就要加1了
它的右數
level要加1
透過遞回的方式去呼叫
這樣DFS的一個
遞回函數呢就很快就可以完成
然後在18行的地方我們再去呼叫
那接下來我們就考慮答案
就是當你的SZ呢
是小於K的時候答案當然就-1
那
在其他情況那我們當然就是用
Python當中的
heap queue裡面當中的n
larges
然後這樣一個一個方法
那當然是DK一個
然後作用在
呃
sum這個list
當然我們只要考慮前面SZ一個就可以了
它當然是當中的最後一個
好
所以這是
Python版的
那我們把這拉高一點
好我們讓它
編譯
我們讓它執行一次
好這兩個case都ok
submit
好所以它的速度其實是蠻快的
好
大概
呃73毫秒
啊打敗Python3的使用者
達98.12%
好
好那我們再看其他的版本
C++的版本那我們這邊的
呃陣列我們就採用C陣列
啊比較單純一點
我們就
不一定要用vector
那它也會比較快一些
那這這裡的寫法其實就跟剛剛的說明是一致的
所以我們讓它執行
然後submit
好我們看看
那它的速度是很快11毫秒
啊打敗
99.80%的
呃C++的使用者
那我們再看一下左邊這邊的我們所
公佈的解答
那另外一種做法當然是可以
考慮所謂的BFS的方式
那我們這邊是有採採用所謂的hip的方式
當然也不一定是用hip
你更當然可以考慮
呃就是用後面也採用
nth element這樣的一個方式
那這個這邊的話我們是呈現在這邊
好
那
好那我們就先談到這裡