不明白二叉树最大路径和问题的解法
Do not understand the solution for the Binary Tree Maximum Path Sum problem
GeeksforGeeks 网站针对二叉树的最大路径和问题提出了 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:
- Node only
- Max path through Left Child + Node
- Max path through Right Child + Node
- Max path through Left Child + Node + Max path through Right Child
特别是，当我们变量res.val包含我们感兴趣的答案时，我不明白为什么在函数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.
有人可以为解决方案的这一步提供解释吗？
您缺少 res.val 的值。该算法尝试探索整棵树，使用 res.val 等于迄今为止探索的最大路径长度。在每一步中，它递归遍历子项并更新 res.val 最大路径长度，如果大于已经存在的路径长度。
证明：
假设您的算法适用于高度为 n 的树。对于高度为 n+1 的树，有一个根和 2 个高度为 n 的子树。还要考虑 findMaxUtil 对于 i<=n 工作正常，并且 return 最大路径，从子树的部分根开始。
所以你的树中高度为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).
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() 确实做了 两个 事情：returns 它所应用的树的最大总和，并且 它更新一个变量，该变量跟踪迄今为止遇到的最大总和。原始代码中对此有评论，但您在问题中将其编辑掉了，也许是为了简洁：
// 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。在最后一行返回该值是此函数所做的 one 事情。第二行和第三行查看该值并考虑它或包含两者的路径 children 是否大于任何先前看到的路径，如果是，它更新 res，即 other 这个函数做的事情。请记住，res 是存在于 方法 之外的一些 object，因此对它的更改会一直持续到递归停止并且 findMaxSum(Node) 开始整个事情，returns res.val.
所以，回到顶部的问题，findMaxUtil returns max_single 的原因是它使用该值递归地确定通过每个子树的最大路径. res 中的值 也 已更新，以便 findMaxSum(Node) 可以使用它。
老实说，我认为那个网站上的描述很不清楚。我会尽力让您相信算法背后的推理。
我们有一个二叉树，节点的值为：
我们正在寻找那棵树中的一条路径，一条连接节点的链。
因为它是一棵有向树，任何非空路径由一个lowest-depth节点组成（即路径中最接近树根的节点） ，零个或多个节点的路径下降到 lowest-depth 节点的左侧，零个或多个节点的路径下降到 lowest-depth 节点的右侧。特别是，在树的某处有一个节点是最大路径中的 lowest-depth 节点。 （事实上 ，可能有不止一条这样的路径具有相同的价值，并且它们可能每个都有自己不同的 lowest-depth 节点。没关系。只要至少有一个，这就是最重要的。）
（我在图表中使用了“最高”，但我的意思是“lowest-depth”。要明确的是，任何时候我使用“深度”或“下降”我都在谈论位置树。任何时候我使用“最大值”我都在谈论一个节点的值或路径中节点值的总和。）
所以如果我们能找到它的 lowest-depth 节点，我们就知道最大值路径由节点本身组成，零个或多个节点的 sub-path 从它的左边下降（包括） child，以及 sub-path 的零个或多个节点从其右侧 child 下降（包括）。一步之遥得出结论，左右下降路径一定是每边这种下降路径的最大值。 （如果这不是很明显，请考虑您选择的任何其他路径，您可以将总值增加 而不是 选择该侧的最大值下降路径。）如果其中一个或两个这些路径将具有负值，那么我们根本不在负侧包含任何节点。
所以我们有一个单独的子问题 - 给定一棵子树，通过其根递减的最大值路径的值是多少？好吧，如果以其 children 为根的所有路径的总和为负，或者如果它 has 没有 children，那么它可能只是根本身。否则它是根加上以其 children 为根的任何一个的最大值下降路径。这个子问题可以很容易地单独回答，但是为了避免重复遍历和重做工作，我们将把它们合并到树的一次遍历中。
回到正题，我们知道some节点就是最大值路径中的lowest-depth节点。我们甚至并不特别关心知道什么时候访问它 - 我们只是要递归访问 每个 节点并找到具有该路径的最大值路径作为其 lowest-depth 节点，确保在某个时候我们将访问我们想要的那个。在每个节点，我们计算 both 从该点开始并在子树 (max_single) 内下降的最大值路径 和 最大值此节点是路径中的 lowest-depth 节点的路径 (max_top)。后者是通过获取节点并“粘贴”零个、最大 descending-only 路径中的一个或两个通过其 children 找到的。 （由于 max_single 已经是从零或 children 之一下降的最大值路径，我们唯一需要考虑的额外事情是通过两个 children 的路径。）通过在每个节点计算 max_top 并保留在 res.val 中找到的最大值，我们保证在完成遍历树时我们将找到所有值中的最大值。在每个节点，我们 return max_single 用于 parent 的计算。在算法的最后，我们只是从 res.val.
中提取答案
GeeksforGeeks 网站针对二叉树的最大路径和问题提出了 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:
- Node only
- Max path through Left Child + Node
- Max path through Right Child + Node
- Max path through Left Child + Node + Max path through Right Child
特别是，当我们变量res.val包含我们感兴趣的答案时，我不明白为什么在函数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.
有人可以为解决方案的这一步提供解释吗？
您缺少 res.val 的值。该算法尝试探索整棵树，使用 res.val 等于迄今为止探索的最大路径长度。在每一步中，它递归遍历子项并更新 res.val 最大路径长度，如果大于已经存在的路径长度。
证明：
假设您的算法适用于高度为 n 的树。对于高度为 n+1 的树，有一个根和 2 个高度为 n 的子树。还要考虑 findMaxUtil 对于 i<=n 工作正常，并且 return 最大路径，从子树的部分根开始。
所以你的树中高度为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).
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() 确实做了 两个 事情：returns 它所应用的树的最大总和，并且 它更新一个变量，该变量跟踪迄今为止遇到的最大总和。原始代码中对此有评论，但您在问题中将其编辑掉了，也许是为了简洁：
// 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。在最后一行返回该值是此函数所做的 one 事情。第二行和第三行查看该值并考虑它或包含两者的路径 children 是否大于任何先前看到的路径，如果是，它更新 res，即 other 这个函数做的事情。请记住，res 是存在于 方法 之外的一些 object，因此对它的更改会一直持续到递归停止并且 findMaxSum(Node) 开始整个事情，returns res.val.
所以，回到顶部的问题，findMaxUtil returns max_single 的原因是它使用该值递归地确定通过每个子树的最大路径. res 中的值 也 已更新，以便 findMaxSum(Node) 可以使用它。
老实说，我认为那个网站上的描述很不清楚。我会尽力让您相信算法背后的推理。
我们有一个二叉树，节点的值为：
我们正在寻找那棵树中的一条路径，一条连接节点的链。
因为它是一棵有向树，任何非空路径由一个lowest-depth节点组成（即路径中最接近树根的节点） ，零个或多个节点的路径下降到 lowest-depth 节点的左侧，零个或多个节点的路径下降到 lowest-depth 节点的右侧。特别是，在树的某处有一个节点是最大路径中的 lowest-depth 节点。 （事实上 ，可能有不止一条这样的路径具有相同的价值，并且它们可能每个都有自己不同的 lowest-depth 节点。没关系。只要至少有一个，这就是最重要的。）
（我在图表中使用了“最高”，但我的意思是“lowest-depth”。要明确的是，任何时候我使用“深度”或“下降”我都在谈论位置树。任何时候我使用“最大值”我都在谈论一个节点的值或路径中节点值的总和。）
所以如果我们能找到它的 lowest-depth 节点，我们就知道最大值路径由节点本身组成，零个或多个节点的 sub-path 从它的左边下降（包括） child，以及 sub-path 的零个或多个节点从其右侧 child 下降（包括）。一步之遥得出结论，左右下降路径一定是每边这种下降路径的最大值。 （如果这不是很明显，请考虑您选择的任何其他路径，您可以将总值增加 而不是 选择该侧的最大值下降路径。）如果其中一个或两个这些路径将具有负值，那么我们根本不在负侧包含任何节点。
所以我们有一个单独的子问题 - 给定一棵子树，通过其根递减的最大值路径的值是多少？好吧，如果以其 children 为根的所有路径的总和为负，或者如果它 has 没有 children，那么它可能只是根本身。否则它是根加上以其 children 为根的任何一个的最大值下降路径。这个子问题可以很容易地单独回答，但是为了避免重复遍历和重做工作，我们将把它们合并到树的一次遍历中。
回到正题，我们知道some节点就是最大值路径中的lowest-depth节点。我们甚至并不特别关心知道什么时候访问它 - 我们只是要递归访问 每个 节点并找到具有该路径的最大值路径作为其 lowest-depth 节点，确保在某个时候我们将访问我们想要的那个。在每个节点，我们计算 both 从该点开始并在子树 (max_single) 内下降的最大值路径 和 最大值此节点是路径中的 lowest-depth 节点的路径 (max_top)。后者是通过获取节点并“粘贴”零个、最大 descending-only 路径中的一个或两个通过其 children 找到的。 （由于 max_single 已经是从零或 children 之一下降的最大值路径，我们唯一需要考虑的额外事情是通过两个 children 的路径。）通过在每个节点计算 max_top 并保留在 res.val 中找到的最大值，我们保证在完成遍历树时我们将找到所有值中的最大值。在每个节点，我们 return max_single 用于 parent 的计算。在算法的最后，我们只是从 res.val.