二叉树最大路径和算法

huangapple go评论73阅读模式
英文:

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;
    }
}

参考资料

  • 欲获取更多详细信息,请参阅讨论区,您可以在那里找到许多良好解释的已接受解决方案,包括各种语言,以及高效算法和渐近时间/空间复杂性分析<sup>12</sup>。
英文:

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

  • For additional details, please see the Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis<sup>1, 2</sup>.

huangapple
  • 本文由 发表于 2020年8月10日 03:02:19
  • 转载请务必保留本文链接:https://go.coder-hub.com/63330222.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定