二叉树最长根到叶子路径节点和计算结果错误排查

问题描述 #

题目要求：给定一棵大小为N的二叉树，实现函数sumOfLongRootToLeafPath()，找出从根到叶子的最长路径上所有节点的和。若存在多条最长路径，选择节点和最大的那条。

示例1输入：

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

输出应为13，解释：最长路径为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、r.sum时发现左右子树的这些值始终相同，怀疑回溯时左子树的结果被干扰，请问代码错误在哪里？

错误原因 #

你在递归过程中始终复用同一个Info对象，导致左子树递归修改的count和sum会被右子树的递归操作覆盖。因为l和r都是传入的同一个ans对象的引用，左右子树的递归操作其实都是在修改同一个实例的属性，最终导致左右子树的信息完全相同，无法正确比较路径长度和和。

修正方案 #

递归时不要复用传入的Info对象，而是每次递归都创建新的Info实例来存储当前子树的路径长度和节点和，保证左右子树的信息相互独立。

修正后的代码 #

class Solution
{
    class Info
    {
        int count;
        int sum;
        Info(int count,int sum)
        {
            this.count = count;
            this.sum = sum;
        }
    }
    
    public Info findSum(Node root)
    {
        if(root == null)
        {
            // 空节点返回路径长度0，和为0
            return new Info(0, 0);
        }
        
        // 递归获取左右子树的信息，各自是独立的Info实例
        Info leftInfo = findSum(root.left);
        Info rightInfo = findSum(root.right);
        
        if(leftInfo.count > rightInfo.count)
        {
            // 左路径更长，当前节点的路径长度+1，和累加当前节点值
            return new Info(leftInfo.count + 1, leftInfo.sum + root.data);
        }
        else if(leftInfo.count < rightInfo.count)
        {
            // 右路径更长，同理处理
            return new Info(rightInfo.count + 1, rightInfo.sum + root.data);
        }
        else
        {
            // 路径长度相同，选和更大的那条，再累加当前节点值
            return new Info(leftInfo.count + 1, Math.max(leftInfo.sum, rightInfo.sum) + root.data);
        }
    }
    
    public int sumOfLongRootToLeafPath(Node root)
    {
        if(root == null)
            return 0;
        
        return findSum(root).sum;
    }
}

修正说明 #

1. 移除了findSum方法中传入的Info参数，改为每次递归返回新的Info实例，确保左右子树的信息不会互相覆盖。
2. 空节点直接返回新的Info(0,0)，避免修改外部对象。
3. 处理当前节点时，根据左右子树的Info实例计算当前路径的长度和和，返回新的Info对象传递给上层递归。

这样修改后，针对示例测试用例就能正确计算出最长路径的和为13。

内容的提问来源于stack exchange，提问作者Mr. Doggo