从根节点到叶节点的最长路径上的节点之和返回错误

Question

我正在尝试解决GeeksforGeeks问题从根到叶节点最长路径上的节点总和：

给定一个大小为 N 的二叉树。您的任务是完成函数

sumOfLongRootToLeafPath()

，即找到从根节点到叶节点的最长路径上所有节点的总和。

如果两条或更多路径竞争最长路径，则考虑节点总数最大的路径。

示例1：

输入：

        4        
       / \       
      2   5      
     / \ / \     
    7  1 2  3    
      /
     6

输出：13

说明：

        4        
       / \       
      2   5      
     / \ / \     
    7  1 2  3 
      /
     6

上面突出显示的节点 (4, 2, 1, 6) 是 最长的根到叶路径的一部分 总和 = (4 + 2 + 1 + 6) = 13

这是我正在尝试使用的代码：

class Solution
{
    class Info
    {
        int count;
        int sum;
        Info(int count,int sum)
        {
            this.count=count;
            this.sum=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

的值进行测试时，有是有问题的，因为

l

和

r

的值始终相同。我认为在回溯左子树的

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;
    }
}