不明白二叉树最大路径和问题的解法
GeeksforGeeks 网站提出了二叉树最大路径和问题的解决方案。问题如下：
给定一棵二叉树，求最大路径和。路径可以在树中的任何节点开始和结束。
解决方案的核心如下：
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;
我相信上面的代码遵循这个逻辑，但我不明白为什么这个逻辑是正确或有效的：
对于每个节点，最大路径可以通过四种方式通过节点：
- 仅节点
- 通过左子节点 + 节点的最大路径
- 通过右子节点 + 节点的最大路径
- 通过左子节点的最大路径 + 节点 + 通过右子节点的最大路径
特别是，我不明白为什么当我们变量包含我们感兴趣的答案时max_single，函数中会返回。 网站上给出了以下原因，但我不明白：findMaxUtilres.val
需要注意的重要一点是，每个子树的根都需要返回最大路径和，以便最多涉及根的一个子节点。
有人可以为解决方案的这一步提供解释吗？
回答
特别是，当我们变量 res.val 包含我们感兴趣的答案时，我不明白为什么在函数 findMaxUtil 中返回 max_single 。
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)
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;
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.
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.