网站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;
我认为上面的代码遵循这个逻辑，但我不明白为什么这个逻辑是正确或有效的：
对于每个节点，最大路径可以通过以下四种方式之一经过该节点：
- 仅通过节点
- 通过左子节点最大路径 + 节点
- 通过右子节点最大路径 + 节点
- 通过左子节点最大路径 + 节点 + 通过右子节点最大路径
特别地，我不明白为什么在函数findMaxUtil中返回max_single，而不是变量res.val包含我们感兴趣的答案。网站上给出了以下原因，但我不理解：
需要注意的重要一点是，每个子树的根节点都需要返回最大路径和，使得根节点的最多一个子节点参与其中。
有人能为这个解决方案的步骤提供解释吗？
findMaxUtil是一个递归函数。在这里，res用于跟踪整体最大值，该值将在调用findMaxUtil时传递，并随后用于在树节点上进行遍历时与路径和进行比较。当语言支持时，另一种方法是将res作为全局变量。 - Agusint findMaxUtil(Node node, Res res)）中所提供的那样。顺便提一下，不能使用原始类型变量来做到这一点。另一种方式是通过在同一类上创建静态变量。最后一种方法是为findMaxUtil创建一个特定的类作为返回值，该类将保存max_single和“res”两个参数。 - Agus左+当前节点、右+当前节点、当前节点、左+右+当前节点和最大路径和或res。比较这5个值将产生新的最大路径和/res。如果我们观察到，这里考虑了当前节点，因为一个节点可能有负值，所以当前节点数据仍然可能大于当前节点+左或当前节点+右。 - Agus