二叉树中最小级别的所有叶节点之和

Question

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

例子：

对于上述二叉树，返回100（40 60）

（图片来源：Geeksforgeks）

Answer 1

你也可以使用map，minLeafSum是驱动函数，逻辑很简单。只需浏览代码。

void getmin(map<int,vector<int>> &m,Node* root,int level)
{
    if(root==NULL)
        return;
    if(root->left==NULL && root->right==NULL)
    {
        m[level].push_back(root->data);
        return;
    }
    if(root->left!=NULL)
        getmin(m,root->left,level+1);
    if(root->right!=NULL)
        getmin(m,root->right,level+1);
}
int minLeafSum(Node* root)
{
    int ans=0;

    map<int,vector<int>> m;
    getmin(m,root,0);
    auto it = m.begin();
    for(int i=0; i< it->second.size() ;i++)
        ans += it->second[i];

    return ans ;
}

Answer 2

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

函数返回一对值，其中第一个值是最小叶级别，第二个值是该级别上叶元素的总和。