Geeksforgeks网站为二叉树的最大路径和问题提供了一个解决方案。问题如下：
给定一棵二叉树，求最大路径和。路径可以从树中的任何节点开始和结束。
解决方案的核心如下：
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` 正在函数中返回 `findMaxUtil` 当我们计算变量 `res.val` 包含我们感兴趣的答案。网站上给出了以下原因，但我不明白：
需要注意的一点是，每个子树的根需要返回最大路径和，这样最多只涉及根的一个子树。
有人能解释一下这个步骤吗？
3条答案
按热度按时间bvjveswy1#
特别是，我不明白当变量res.val包含我们感兴趣的答案时，为什么在函数findmaxutil中返回max\u single。
问题是
findMaxUtil()真正做两件事：它返回它应用到的树的最大和，并更新一个变量来跟踪遇到的最大和。在原始代码中有这样一个注解，但您在问题中编辑了它，也许是为了简洁：因为java按值传递参数，但是java中的每个对象变量都隐式引用实际对象，所以很容易忽略
Res那已经过去了res此函数可以更改参数。这正是你问的台词中发生的事情：第一行找到节点本身的最大值或节点加上最大子树的最大值，结果就是
max path sum going through root. 在最后一行返回这个值是这个函数要做的一件事。第二行和第三行查看该值，并考虑该值或包含两个子项的路径是否大于先前看到的任何路径，如果大于，则更新该值res，这是该函数所做的另一件事。请记住res是存在于方法外部的某个对象，因此对它的更改将一直保留，直到递归停止并findMaxSum(Node)，开始了整个过程，返回res.val.所以，回到最上面的问题
findMaxUtil退货max_single它使用该值递归地确定通过每个子树的最大路径。中的值res也进行了更新，以便findMaxSum(Node)我可以用它。hsvhsicv2#
你错过了
res.val. 该算法试图探索整个树，使用res.val等于在此之前探索的最大路径长度。在每个步骤中，它递归地遍历子级并更新res.val最大路径长度，如果高于已经存在的路径长度。证明：
假设您的算法适用于具有高度的树
n. 对于有高度的树n+1有一个根和两个子树的高度n. 还要考虑一下findMaxUtil适用于i<=n并将返回最大路径，从子树的部分根开始。所以你树上的最大路径
n+1计算如下findMaxUtil(subtree1)
findMaxUtil(subtree2)findmaxUtil(subtree1)+root.datafindmaxUtil(subtree2)+root.datafindmaxUtil(subtree1)+findmaxUtil(subtree2)+root.datares.val最后的结果是：findmaxUtil(newTree)=max(items 1:6).4c8rllxm3#
老实说，我认为网站上的描述很不清楚。我会尽我所能让你相信算法背后的道理。
我们有一个二叉树，节点上有值：
我们在树上寻找一条路径，一条连接节点的链。
由于它是一个有向树，任何非空路径都由一个最低深度节点（即路径中距离树的根最近的节点）组成，一个由零个或多个节点组成的路径下降到最低深度节点的左侧，一个由零个或多个节点组成的路径下降到最低深度节点的右侧。特别地，在树的某个地方有一个节点，它是最大路径中深度最低的节点(实际上，可能有多条这样的路径被绑定为相等的值，并且它们可能都有各自不同的最低深度节点。那很好。只要至少有一个，这才是最重要的。）
（我在图表中使用了“最高”，但我的意思是“最低深度”。要清楚的是，每当我使用“深度”或“下降”时，我指的是树中的位置。每当我使用“maximum”时，我指的是一个节点的值或路径中节点值的总和。）
因此，如果我们能找到它的最低深度节点，我们知道最大值路径是由节点本身，一个由零个或多个节点组成的从（包括）它的左子节点下降的子路径，和一个由零个或多个节点组成的从（包括）它的右子节点下降的子路径组成的。这是一个很小的步骤，以得出结论，左，右下降路径必须是最大值这样的下降路径在每一边(如果这一点不明显，请考虑您选择的任何其他路径，您可以通过选择该侧的最大值降序路径来增加总值。）如果其中一条或两条路径的值都为负值，则在负侧根本不包含任何节点。
所以我们有一个单独的子问题-给定一个子树，最大值路径通过它的根下降的值是多少？好吧，它可能只是根本身，如果根在它的子路径上的所有路径都有负和，或者如果它没有子路径。否则，它是根加上根在其子级上的任何一个的最大值降序路径。这个子问题可以很容易地自己解决，但是为了避免重复遍历和重做工作，我们将把它们结合到树的一次遍历中。
回到主要问题，我们知道一些节点是最大值路径中深度最低的节点。我们甚至不特别关心何时访问它—我们只是递归地访问每个节点，并找到最大值路径，该路径作为其最低深度节点，确保在某个点我们将访问我们想要的。在每个节点上，我们计算从该点开始的最大值路径和子树内的下降路径(
max_single)以及最大值路径，对于该路径，该节点是路径中深度最低的节点(max_top). 后者是通过取节点并“粘上”零来找到的，即通过其子节点的一条或两条最大降序路径(自max_single已经是从0或其中一个子级开始的最大值路径，我们需要考虑的唯一额外的事情是通过两个子级的路径。）max_top在每个节点上保持res.val，我们保证在遍历完树时，将找到所有值中最大的值。在我们返回的每个节点max_single在父计算中使用。在算法的最后，我们从res.val.