gfg问题：从根节点到叶节点最长路径上的节点之和

Question

类解决方案 { 班级信息 { 整数计数； 整数总和； 信息（整数计数，整数总和） { this.count=计数； this.sum=总和； } }

public Info findSum(Node root,Info ans)
{
    if(root==null)
    {
        ans.count=0;
        ans.sum=0;
       
        return ans;
    }
    
    Info l=findSum(root.left,ans);
    Info r=findSum(root.right,ans);
    
    //System.out.println(l.count + " " + l.sum+"     "+r.count+" "+ r.sum);
     
    if(l.count>r.count)
    {
        ans.count=l.count+1;
        ans.sum=l.sum+root.data;
    }
    else if(l.count<r.count)
    {
        ans.count=r.count+1;
        ans.sum=r.sum+root.data;
    }
    else
    {
        ans.count=l.count+1;
        ans.sum=Math.max(l.sum,r.sum)+root.data;
    }
    // System.out.println(ans.count+" "+ans.sum);
    // System.out.println();
    //System.out.println();
    return ans;
    
}
public int sumOfLongRootToLeafPath(Node root)
{
    if(root==null )
    return 0;
    
    Info ans=new Info(0,0);
    return findSum(root,ans).sum;
}

} 它给出的输出为 12，而正确的输出是 13。我已经试运行了很多次，但在逻辑中找不到任何错误...同时通过打印 l.count、l.sum 的值来测试它，r.count ...执行期间出现问题。我不知道在哪里。请有人调查并纠正我。 测试用例输入：4 2 5 7 1 2 3 N N 6 N 输出：13 我的输出：12 （我附上了输入格式的ss）

我认为，在回溯左子树的 ans 时，不知何故，它变得混乱了。请解释一下。

Answer 1

问题是你只有一个

ans

对象，该对象会被函数的所有执行写入，即使已经在其中写入了潜在的最佳解决方案。它只是被次优解决方案再次覆盖（甚至在下一个访问的叶子处设置为零）。这也意味着当您进行两次递归调用时，

l

和

r

都是相同的：它们与

ans

相同。这当然不是你想要的。

使用

ans

作为只写参数的方式没有用，因为你还返回该对象。您可能根本没有该参数。

相反，让基本情况 create 一个新的

Info

实例，以便

l

和

r

将是不同的对象，然后决定两者中哪一个是“最好的”，然后使用当前节点的数据并返回 that 对象。

这是用这个想法修正的代码：

class Solution
{
    class Info
    {
        int count;
        int sum;
        
        Info(int count, int sum)
        {
            this.count = count;
            this.sum = sum;
        }
    }
    
    public Info findSum(Node root) // No extra argument
    {
        if (root == null)
        {
            return new Info(0, 0); // New, distinct instance!
        }
        
        Info l = findSum(root.left);
        Info r = findSum(root.right);
        
        // Select the "best" one
        if (l.count > r.count || l.count == r.count && l.sum > r.sum)
        {
            r = l;
        }
        // Upgrade it to take into account the current node
        r.count++;
        r.sum += root.data;
        return r;
        
    }
    
    public int sumOfLongRootToLeafPath(Node root)
    {
        return findSum(root).sum;
    }
}