java不了解二叉树最大路径和问题的解决方案

Question

Geeksforgeks网站为二叉树的最大路径和问题提供了a solution。问题如下:

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

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

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; 

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

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

1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

特别是，我不明白为什么在变量res.val包含我们感兴趣的答案时max_single会在函数findMaxUtil中返回max_single。网站上给出了以下原因，但我不理解：

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.

有人能解释一下解决方案的这一步吗

Answer 1

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()确实做了两件事：它返回应用到的树的最大和，和它更新一个变量来跟踪遇到的最大和。原始代码中有这样一条注释，但您在问题中删去了它，可能是为了简洁：

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

因为Java passes parameters by value, but every object variable in Java implicitly references the actual object，很容易忽略这样一个事实，即在res参数中传递的Res可以通过该函数更改。这正是你所问的那句台词中发生的事情：

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 path sum going through root。在最后一行返回该值是该函数所做的一件事。第二行和第三行查看该值，并考虑它是否包含两个孩子的路径大于任何先前看到的路径，如果是，则更新^ {CD3}}，这是该函数的其他。请记住res是存在于方法之外的某个对象，因此对它的更改将一直持续到递归停止为止，而启动整个过程的findMaxSum(Node)将返回res.val

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

Answer 2

老实说，我认为该网站上的描述非常不清楚。我会尽我所能让你相信算法背后的道理

我们有一个二叉树，节点上有值：

我们在树中寻找一条路径，一条连接节点链

由于它是一个有向树，任何非空路径由一个最低深度节点（即路径中最接近树根的节点）、一个从最低深度节点左侧下降的零个或多个节点的路径以及从最低深度节点右侧下降的零个或多个节点的路径组成。特别是，在树的某个地方有一个节点，它是最大路径中深度最低的节点。（事实上，可能有不止一条这样的路径被绑定为相等的值，它们可能都有各自不同的最低深度节点。这很好。只要至少有一条，这就是问题所在。）

（我在图中使用了“highest”，但我的意思是“lowest depth”。更清楚地说，每当我使用“depth”或“downing”时，我指的是树中的位置。每当我使用“maximum”时，我指的是一个节点的值或路径中节点的值之和。）

因此，如果我们能找到它的最低深度节点，我们知道最大值路径由节点本身、从（包括）其左子节点向下的零个或多个节点的子路径以及从（包括）其右子节点向下的零个或多个节点的子路径组成。这是一小步，可以得出这样的结论：左侧和右侧的下降路径必须是最大值，例如每侧的下降路径。（如果这不是显而易见的，考虑你选择的其他路径，你可以通过EME来增加总价值，而不是ESE>选择那个边上的最大值下降路径。）如果这些路径中的一个或两个都有负值，那么我们就根本不在负值侧包含任何节点

所以我们有一个单独的子问题-给定一个子树，通过它的根下降的最大值路径的值是多少？好的，它可能只是根本身，如果所有根在它的子路径都有负和，或者如果它没有子路径。否则，它是根加上在其子级上根的任何一个的最大值下降路径。这个子问题可以很容易地自行解决，但为了避免重复遍历和重做工作，我们将把它们结合到树的一次遍历中

回到主要问题，我们知道某些节点是最大值路径中深度最低的节点。我们甚至不特别关心何时访问它——我们只是递归地访问每个节点，找到最大值路径，该路径作为其最低深度节点，确保在某个时候我们将访问我们想要的路径。在每个节点上，我们计算从该点开始并在子树（max_single）中下降的最大值路径（max_single）和最大值路径，该节点是路径中深度最低的节点（max_top）。后者是通过获取节点并“粘合”零、一条或两条通过其子节点的最大降序路径来找到的。（因为{{CD1}}已经是从零或一个孩子下降的最大值路径，我们需要考虑的唯一额外的事情是通过两个孩子的路径。）通过计算每个节点上的max_top并保持在res.val中找到的最大值，我们保证在完成遍历树时找到所有值中的最大值。在每个节点上，我们返回max_single以用于父节点的计算。在算法的最后，我们从res.val中取出答案

Answer 3

您缺少res.val的值。该算法试图探索整个树，使用res.val等于在此之前探索的最大路径长度。在每个步骤中，它递归地遍历子级，并使用最大路径长度更新res.val，如果该路径长度高于已经存在的路径长度

证明：

假设您的算法适用于高度为n的树。对于高度为n+1的树，有一个根和两个高度为n的子树。还考虑到{{CD7}}对于^ {< CD8> }工作良好，并且将从子树的部分根开始返回最大路径。

因此，树中高度为n+1的最大路径计算如下

1. findMaxUtil(subtree1)
2. findMaxUtil(subtree2)
3. findmaxUtil(subtree1)+root.data
4. findmaxUtil(subtree2)+root.data
5. findmaxUtil(subtree1)+findmaxUtil(subtree2)+root.data
6. res.val

最后的结果是：findmaxUtil(newTree)=max(items 1:6)