java - 在二叉树中最大和路径的解决方案中查找错误

Question

问题是:

给定一棵二叉树，找到最大路径总和。

路径可以在树中的任何节点开始和结束。

示例:

给定二叉树:

   1
  / \
 2   3

返回 6。

我最初的解决方案是:在 LeetCode 上通过了 90/92 的测试用例

public class Solution {

    int max = Integer.MIN_VALUE;//This is to handle the scenario where the value of all nodes is negative

    public int maxPathSum(TreeNode a) {

        if(a == null){
            return 0;
        }

        int sum = maxSum(a);

        return max > sum ? max : sum;
    }

    public int maxSum(TreeNode node){

        if(node == null){
            return 0;
        }

        //handling the scenario where sum of any path is not greater than the value of single node
        if(node.val > max){
            max = node.val;
        }

        int leftChildSum = maxSum(node.left);

        //path from current node to left child is maximum
        if(node.val + leftChildSum > max){
            max = node.val + leftChildSum;
        }

        int rightChildSum = maxSum(node.right);

        //path from current node to right child is maximum
        if(node.val + rightChildSum > max){
            max = node.val + rightChildSum;
        }

        ////path from left child to right child via current node is maximum
        if(node.val + leftChildSum + rightChildSum > max){
            max = node.val + leftChildSum + rightChildSum;
        }

        return Math.max(node.val + leftChildSum, node.val + rightChildSum);
    }
}

但我认为这个解决方案应该修改。
考虑一个场景，其中节点具有正值，并且其 leftChildSum 和 rightChildSum 均为负值。在这种情况下，应该返回节点的值。

修改后的解决方案:在 LeetCode 上通过了 63/92 个测试用例

public class Solution {

    int max = Integer.MIN_VALUE;//This is to handle the scenario where the value of all nodes is negative

    public int maxPathSum(TreeNode a) {

        if(a == null){
            return 0;
        }

        int sum = maxSum(a);

        return max > sum ? max : sum;
    }

    public int maxSum(TreeNode node){

        if(node == null){
            return 0;
        }

        //handling the scenario where sum of any path is not greater than the value of single node
        if(node.val > max){
            max = node.val;
        }

        int leftChildSum = maxSum(node.left);

        //path from current node to left child is maximum
        if(node.val + leftChildSum > max){
            max = node.val + leftChildSum;
        }

        int rightChildSum = maxSum(node.right);

        //path from current node to right child is maximum
        if(node.val + rightChildSum > max){
            max = node.val + rightChildSum;
        }

        ////path from left child to right child via current node is maximum
        if(node.val + leftChildSum + rightChildSum > max){
            max = node.val + leftChildSum + rightChildSum;
        }

        //Changes are below
        int temp = node.val;
        int value = Math.max(temp, node.val + leftChildSum);
        value = Math.max(temp, node.val + rightChildSum);
        return value;

    }
}

有人可以帮我找出修改后的解决方案有什么问题吗？

Answer 1

第二个解决方案有一个小错误:

而不是写:

int value = Math.max(temp, node.val + leftChildSum);

value = Math.max(temp, node.val + rightChildSum);

我应该写:

int value = Math.max(temp, node.val + leftChildSum);

value = Math.max(value, node.val + rightChildSum);