不了解二叉树最大路径和问题的解决方案 [英] Do not understand the solution for the Binary Tree Maximum Path Sum problem

问题描述

GeeksforGeeks网站已经提供了解决方案有关二叉树的最大路径总和的问题.问题如下:

The website GeeksforGeeks has presented a solution for the problem of Maximum path sum for a binary tree. The question is as follows:

给出一棵二叉树，找到最大路径总和.路径可能会开始，结束于树中的任何节点.

Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

解决方案的核心如下:

int findMaxUtil(Node node, Res res) 
{ 
  
    if (node == null) 
        return 0; 
  
    // l and r store maximum path sum going through left and 
    // right child of root respectively 
    int l = findMaxUtil(node.left, res); 
    int r = findMaxUtil(node.right, res); 
  
    // Max path for parent call of root. This path must 
    // include at-most one child of root 
    int max_single = Math.max(Math.max(l, r) + node.data, 
                              node.data); 
  
  
    // Max Top represents the sum when the Node under 
    // consideration is the root of the maxsum path and no 
    // ancestors of root are there in max sum path 
    int max_top = Math.max(max_single, l + r + node.data); 
  
    // Store the Maximum Result. 
    res.val = Math.max(res.val, max_top); 
  
    return max_single; 
} 

int findMaxSum() { 
    return findMaxSum(root); 
 } 
  
// Returns maximum path sum in tree with given root 
int findMaxSum(Node node) { 
  
    // Initialize result 
    // int res2 = Integer.MIN_VALUE; 
    Res res = new Res(); 
    res.val = Integer.MIN_VALUE; 
  
    // Compute and return result 
    findMaxUtil(node, res); 
    return res.val; 
} 

Res 具有以下定义:

 class Res { 
    public int val; 
}

我对这些代码行背后的推理感到困惑:

I am confused about the reasoning behind these lines of code:

int max_single = Math.max(Math.max(l, r) + node.data, node.data);  

int max_top = Math.max(max_single, l + r + node.data); 

res.val = Math.max(res.val, max_top); 

return max_single; 

我相信上面的代码遵循此逻辑，但我不理解为什么此逻辑正确或有效:

I believe the code above follows this logic but I do not understand WHY this logic is correct or valid:

对于每个节点，最大路径可以通过四种方式通过节点:

For each node there can be four ways that the max path goes through the node:

1. 仅节点
2. 通过左子节点+节点的最大路径
3. 通过右子节点+节点的最大路径
4. 通过左子节点的最大路径+节点+通过右子节点的最大路径

尤其是，当我们变量 res.val 包含答案时，我不明白为什么在功能 findMaxUtil 中返回 max_single 我们感兴趣.网站上给出了以下原因，但我不理解:

In particular, I do not understand why max_single is being returned in the function findMaxUtil when we the variable res.val contains the answer we are interested in. The following reason is given on the website but I do not understand it:

要注意的重要一点是，每个子树的根都需要返回最大路径总和，这样最多会涉及到一个root用户.

An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved.

有人可以为解决方案的这一步骤提供解释吗?

Could someone provide an explanation for this step of the solution?

推荐答案

特别是，当变量res.val包含我们感兴趣的答案时，我不明白为什么在函数findMaxUtil中返回max_single.

In particular, I do not understand why max_single is being returned in the function findMaxUtil when we the variable res.val contains the answer we are interested in.

问题在于， findMaxUtil()确实完成了两项的工作:它返回被应用到的树的最大和，和更新一个变量，以跟踪尚未遇到的最大和.原始代码中对此有一个注释，但是您为简洁起见在问题中对其进行了

The problem is that findMaxUtil() really does two things: it returns largest sum of the tree that it's applied to, and it updates a variable that keeps track of the largest sum yet encountered. There's a comment to that effect in the original code, but you edited it out in your question, perhaps for brevity:

// This function returns overall maximum path sum in 'res' 
// And returns max path sum going through root. 
int findMaxUtil(Node node, Res res) 

因为 Java通过 value 传递参数，但是Java中的每个对象变量都隐式地 references 实际对象，很容易错过这样一个事实，即通过 res 参数传递的 Res 可能会被更改此功能.这正是您所询问的行中发生的事情

Because Java passes parameters by value, but every object variable in Java implicitly references the actual object, it's easy to miss the fact that the Res that's passed in the res parameter may be changed by this function. And that's exactly what happens in the lines you asked about:

int max_single = Math.max(Math.max(l, r) + node.data, node.data);  

int max_top = Math.max(max_single, l + r + node.data); 

res.val = Math.max(res.val, max_top); 

return max_single;

第一行找到节点本身或节点加上最大子树的最大值，结果是通过根的 max路径总和.在最后一行返回该值是此函数执行的一件事.第二行和第三行查看该值，并考虑该值或包含两个子级的路径是否大于以前看到的任何路径，如果是，则更新 res ，即此功能的其他作用.请记住， res 是在方法之外存在的某个对象，因此对它的更改将一直保留，直到递归停止并且 findMaxSum(Node)，整个过程开始，返回 res.val .

That first line finds the maximum of the node itself or the node plus the greatest subtree, and that result is the max path sum going through root. Returning that value on the last line is one thing that this function does. The second and third lines look at that value and consider whether either it or the path that includes both children is larger than any previously seen path, and if so, it updates res, which is the other thing this function does. Keep in mind that res is some object that exists outside the method, so changes to it persist until the recursion stops and findMaxSum(Node), which started the whole thing, returns the res.val.

因此，回到顶部的问题， findMaxUtil 返回 max_single 的原因是它使用该值来递归确定通过每个子树的最大路径. res 中的值也被 更新，以便 findMaxSum(Node)可以使用它.

So, getting back to the question at the top, the reason that the findMaxUtil returns max_single is that it uses that value to recursively determine the max path through each subtree. The value in res is also updated so that findMaxSum(Node) can use it.

这篇关于不了解二叉树最大路径和问题的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！