二叉树最大路径和算法

Question

我不熟悉递归和二叉树。我正在尝试在 leetcode 上解决 this problem。

寻找最大和路径就像寻找任意两个节点之间的最大路径，这条路径可能通过也可能不通过根；除了最大总和路径我们想要跟踪总和而不是路径长度。

我的算法通过了 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;
        }
        //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);
    }
}

Answer 1

尝试

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

Answer 2

我想我们可以稍微简化一下这里的陈述。

这只会被接受：

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

参考资料

有关更多详细信息，请参阅 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^{1, 2}。

二叉树最大路径和算法

Binary Tree Maximum Path Sum Algorithm

java

algorithm

recursion

binary-tree

参考资料