バイナリツリーの最小レベルのすべてのリーフノードの合計

Question

バイナリツリーの最小レベルのすべてのリーフノードの合計を計算する方法。ツリーが存在しない場合は-1を返します。

例：上記バイナリツリーの

、（40 + 60）100を返す

（画像出典：GeeksForGeeks）

Answer 1

f(node, level): 
    if node is null then 
     return { Inf, -1 } 
    if isLeaf(node) then 
     return { level, node.value } 
    fleft <- f(node.left, level + 1) 
    fright <- f(node.right, level + 1) 
    fnode <- { min(fleft.first, fright.first), 0 } 
    if fnode.first = fleft.first then 
     fnode.second <- fnode.second + fleft.second 
    if fnode.first = fright.first then 
     fnode.second <- fnode.second + fright.second 
    return fnode 

関数ペアを返しますここで、firstが最小リーフレベルであり、secondがこのレベルのリーフ要素の合計です。