2个叶子节点之间的最大路径和(GeeksForGeeks)

问题描述 投票：0回答：3

给定一个二叉树，其中每个节点元素都包含一个数字。找到从一个叶节点到另一个叶节点的最大可能总和。

示例1：

Input :      
           3                               
         /    \                          
       4       5                     
      /  \      
    -10   4                          

Output: 16

说明： 最大和位于叶节点 4 和 5 之间。 4 + 4 + 3 + 5 = 16.

示例2：

Input :    
            -15                               
         /      \                          
        5         6                      
      /  \       / \
    -8    1     3   9
   /  \              \
  2   -3              0
                     / \
                    4  -1
                       /
                     10  

Output :  27

说明： 一个叶节点的最大可能总和 另一个是 (3 + 6 + 9 + 0 + -1 + 10 = 27)

这就是解决方案：

'''
# Node Class:
class Node:
    def _init_(self,val):
        self.data = val
        self.left = None
        self.right = None
        '''
res = -999999999
def maxPathSumUtil(root):
    global res
    if root is None:
        return 0
    
    if root.left is None and root.right is None:
        return root.data

    ls=maxPathSumUtil(root.left)
    rs=maxPathSumUtil(root.right)
    
    if root.left and root.right:
        res=max(res,ls+rs+root.data)
        return max(ls+root.data,rs+root.data) #Line: Problem
    if root.left is None:
        return rs+root.data
    else:
        return ls+root.data


def maxPathSum(root):
    global res
    res = -999999999
    maxPathSumUtil(root)
    return res

谁能告诉我为什么我们使用

return max(ls+root.data,rs+root.data)
。如果我们确实使用 
return max(ls+root.data,rs+root.data)
来检查最大值，那么为什么我们要使用 
res=max(res,ls+rs+root.data)
而不仅仅是 
 res = max(ls+root.data,rs+root.data)
。

编辑：

例如：

Let's take this tree for example:

             10
           /   \
         8      2
       /  \
     3     5

在此，递归调用后，

ls
变为3，
rs
变为5。 
res
变为 
ls+rs+root.data
，即 3+5+8 = 16。 那么 
return max(ls+root.data,rs+root.data)
即 max(11,13) = 13。 现在，根据我的说法，函数应该只返回 13，但这种情况并没有发生。尽管 
return
不是递归语句。代码的控制流程是如何发生的？

python algorithm data-structures tree
3个回答
2
投票

执行期间并行测量两件事：

  • ls+rs+root.data
    是以 
    root
    为根的树中位于其下方两片叶子之间的最大路径。所以它是leaf到leaf路径
    • 的（值）
  • 函数返回值是从
    root
    到其下方任何叶子的最大路径。所以它是root-to-leaf路径
    • 的（值）

这是两个不同的概念，不应混淆。

ls
和
rs
都是函数返回值：
ls
表示从
root.left
到叶子的最大路径。同样，
rs
表示从
root.right
到叶子的最大路径。

另一方面，

ls+rs+root.data
表示从叶子到叶子经过
root
的路径。

如果后一个表达式大于

res

，则应更新 
res
，因此为 
max()
。

但是函数的返回值不应该代表叶子到叶子的路径，而是根到叶子的路径。这就是为什么我们有：

return max(ls+root.data,rs+root.data)

这告诉调用者最大根到叶路径是什么，而不是最大叶到叶路径是什么。后者用于确定 

res
，而不是函数的返回值。

我希望这能够澄清这两个概念之间的区别以及它们在算法中扮演的角色。

例子

您以这棵树为例：

         10
       /   \
     8      2
   /  \
 3     5

确实，当为节点 8 调用该函数时，它：

  • 将 
    res
    设置为 16（节点下方两个叶子之间的最大路径）
  • 返回 13（从节点到其叶子节点之一的最大路径）

然后你问：

现在，根据我的说法，函数应该只返回 13，但这种情况并没有发生。

但它确实会这样发生。然而，您不应该忘记这是 

maxPathSumUtil
的返回值，而不是 
maxPathSum
的返回值。另外，这不是 
maxPathSumUtil
的顶级调用。值 13 返回到 
maxPathSumUtil
的另一个执行上下文，其中 
root
是节点 10。然后，在进行另一个递归调用之后（
root
等于节点 2），该顶级执行函数 
maxPathSumUtil
将：

  • 将
    res
    设置为25（节点10以下两个叶子之间的最大路径）
  • 返回23（从节点10到其叶子节点之一的最大路径）

此顶层调用是从 

maxPathSum
内部进行的，它忽略 
maxPathSumUntil
返回的值。 它只取 
res
(25) 的值，并返回 that:

maxPathSumUtil(root)  # notice that return value is ignored.
return res
0
投票

在每个节点，我们必须检查该节点的左右子节点是否产生最大路径。但是当我们返回时，我们需要返回左路径或右路径，具体取决于最大值。 我们以这棵树为例：

         10
       /   \
     8      2
   /  \
 3     5

这样，递归调用后，ls 变为 3，rs 变为 5。res 变为 ls+rs+root.data，即 3+5+8 = 16。因此 res(result) 将更新为 16，return 为max(11,13) 即 13。现在这个 13 值将被节点 10 用作 ls（左值）。

0
投票

从每个节点，需要返回Math.max(left,right)+root.data； 仅当它不是叶节点时才需要计算最大值。每一步都需要进行以上两个操作。

也有一些边缘情况需要处理。我在代码的内联注释中添加了详细信息，以及如果删除这些边缘情况检查，那么对于哪个测试用例它将失败。因此，如果您自己进行一次演练，应该会很清楚。 还建议您在尝试此操作之前练习这些问题。

  1. 二叉树最大路径和
  2. 二叉树的直径

这是解决方案-

class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
} 

class Solution
{
    private Node setTree(Node root){
          Node temp = new Node(0);
          
          //if tree is left most
          if(root.right==null){
              root.right=temp;
          }
          else{    //if tree is right most
              root.left=temp;
          }
          
          return root;
    }
    
    int maxSum=Integer.MIN_VALUE;
     private int getMaxSum(Node root){
        if(root==null) return 0;

        int left=getMaxSum(root.left);
        int right=getMaxSum(root.right);
        
        // [1 8 6 -7 -10 -9], if one of the child is null and other is leaf, we can t return 0 from the null leaf
        if(root.left==null && root.right!=null)
            left=Integer.MIN_VALUE;
        if(root.right==null && root.left!=null)
            right=Integer.MIN_VALUE;

        // difference from leetcoe max path sum is here, we cannot include the root itself even if it has a bigger value
        // since we have to return the sum till leaf from any node, so we need to carry the sum Max(left,right) from leaf
        // and add root to it, even if it reduces the sum
        int temp=Math.max(left,right)+root.data;
        
        // only calculate the max if its not the leaf node
        // [-9,6,10] ans= -13 and not 6
        if(root.left!=null && root.right!=null){
            maxSum=Math.max(maxSum,(left+right+root.data));
        }
        return temp;

    }
    int maxPathSum(Node root)
    { 
        // code here
        if(root.left==null || root.right==null){
            root=setTree(root);
        }
        getMaxSum(root);
        return maxSum;
    } 
}
/*
Some test cases to try out

        //do this only when both left and right are not null
        /*            2
                4           1
            7       10
        n       -3
        
        */ 
        // output -18
        // this also solves this problem, max sum already has a
        // bigger value for non leaf nodes summation
        
        /*      -10
            -1          0
        3
        */ //output -8
*/
最新问题
© www.soinside.com 2019 - 2025. All rights reserved.