英文:
Binary Tree Maximum Path Sum Algorithm
问题
我是递归和二叉树的新手。我正在尝试解决这个问题,在leetcode上。
找到最大和路径就像找到任意两个节点之间的最大路径,该路径可能会经过根节点,也可能不会;除了最大和路径我们想要跟踪的是和而不是路径长度。
我的算法通过了91/93个测试用例,我就是找不出我漏掉了什么。有人可以提供一些指导吗?
class Solution {
private int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
if(root.left != null){
maxPathSumHelper(root.left);
}
if(root.right != null){
maxPathSumHelper(root.right);
}
return sum;
}
public int maxPathSumHelper(TreeNode root){
if(root == null){
return 0;
}
//检查左侧和
int leftValue = root.val + maxPathSumHelper(root.left);
if(leftValue > sum){
sum = leftValue;
}
//检查右侧和
int rightValue = root.val + maxPathSumHelper(root.right);
if(rightValue > sum){
sum = rightValue;
}
//检查如果根值更大
if(root.val > sum){
sum = root.val;
}
//检查右侧和左侧值是否最大
if((leftValue + rightValue - (2 * root.val) )+ root.val > sum){
sum = (leftValue + rightValue - (2 * root.val)) + root.val;
}
return Math.max(leftValue, rightValue);
}
}
英文:
I am new to recursion and binary trees. I am trying to solve this problem on leetcode.
To find maximum sum path is like finding maximum path between any two nodes, that path may or may not pass through the root; except that with max sum path we want to track sum instead of path length.
My algorithm is passing 91/93 test cases and I just can't figure out what I am missing. Can anyone please provide some direction?
class Solution {
private int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
if(root.left != null){
maxPathSumHelper(root.left);
}
if(root.right != null){
maxPathSumHelper(root.right);
}
return sum;
}
public int maxPathSumHelper(TreeNode root){
if(root == null){
return 0;
}
//check left sum
int leftValue = root.val + maxPathSumHelper(root.left);
if(leftValue > sum){
sum = leftValue;
}
//check right sum
int rightValue = root.val + maxPathSumHelper(root.right);
if(rightValue > sum){
sum = rightValue;
}
//check if root value is greater
if(root.val > sum){
sum = root.val;
}
//check if right and left value is the greatest
if((leftValue + rightValue - (2 * root.val) )+ root.val > sum){
sum = (leftValue + rightValue - (2 * root.val)) + root.val;
}
return Math.max(leftValue, rightValue);
}
}
答案1
得分: 3
class Solution {
private int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
if (root.left != null) {
maxPathSumHelper(root.left);
} else if (root.right != null) {
maxPathSumHelper(root.right);
}
return sum;
}
public int maxPathSumHelper(TreeNode root) {
if (root == null) {
return 0;
}
// 检查左边的总和
int leftValue = root.val + maxPathSumHelper(root.left);
if (leftValue > sum) {
sum = leftValue;
}
// 检查右边的总和
int rightValue = root.val + maxPathSumHelper(root.right);
if (rightValue > sum) {
sum = rightValue;
}
// 检查根节点值是否最大
if (root.val > sum) {
sum = root.val;
}
// 检查右边和左边的值是否最大
if ((leftValue + rightValue - (2 * root.val) ) + root.val > sum) {
sum = (leftValue + rightValue - (2 * root.val)) + root.val;
}
return Math.max(Math.max(leftValue, rightValue), root.val);
}
}
英文:
Try
class Solution {
private int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
if (root.left != null) {
maxPathSumHelper(root.left);
} else if (root.right != null) {
maxPathSumHelper(root.right);
}
return sum;
}
public int maxPathSumHelper(TreeNode root) {
if (root == null) {
return 0;
}
//check left sum
int leftValue = root.val + maxPathSumHelper(root.left);
if (leftValue > sum) {
sum = leftValue;
}
//check right sum
int rightValue = root.val + maxPathSumHelper(root.right);
if (rightValue > sum) {
sum = rightValue;
}
//check if root value is greater
if (root.val > sum) {
sum = root.val;
}
//check if right and left value is the greatest
if ((leftValue + rightValue - (2 * root.val) ) + root.val > sum) {
sum = (leftValue + rightValue - (2 * root.val)) + root.val;
}
return Math.max(Math.max(leftValue, rightValue), root.val);
}
}
答案2
得分: 3
这里我们可以稍微简化我们的陈述。
这将会被简单接受:
public final class Solution {
int max;
public final int maxPathSum(final TreeNode root) {
max = Integer.MIN_VALUE;
traverse(root);
return max;
}
private final int traverse(final TreeNode node) {
if (node == null)
return 0;
final int l = Math.max(0, traverse(node.left));
final int r = Math.max(0, traverse(node.right));
max = Math.max(max, l + r + node.val);
return Math.max(l, r) + node.val;
}
}
参考资料
英文:
I guess we can a bit simplify our statements here.
This'll simply get accepted:
public final class Solution {
int max;
public final int maxPathSum(final TreeNode root) {
max = Integer.MIN_VALUE;
traverse(root);
return max;
}
private final int traverse(final TreeNode node) {
if (node == null)
return 0;
final int l = Math.max(0, traverse(node.left));
final int r = Math.max(0, traverse(node.right));
max = Math.max(max, l + r + node.val);
return Math.max(l, r) + node.val;
}
}
References
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论