algorithm - 二叉树中最低级别的所有叶节点的总和

Question

如何计算二叉树中最低级别的所有叶节点的总和。如果不存在树，则它应该返回 -1。

例子:

对于上面的二叉树，返回100(40+60)

(图片来源: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 是该级叶元素的总和。