lc 124.二叉树最大路径和

Question

谁能告诉我如何解释这个特定的测试用例？ 我只是取最大值 0 和递归调用来折扣负节点值

lc 上的测试用例 90 失败

输入根= [-3]

输出0

预计-3

class Solution {
   

    public int maxPathSum(TreeNode root) {
        
        int[] max= new int[1];
        int res = dia(root, max);
        return max[0];


        
    }
    public static int dia(TreeNode root,int[] max){
        if(root==null){
            return 0;
        }
        int lh = Math.max(0,dia(root.left, max));
        int rh =  Math.max(0,dia(root.right, max));

        max[0] = Math.max(max[0], lh+rh+root.val);

        return root.val +  Math.max(lh,rh);


    } 
}

        
    

我遇到了具有负值的节点，并且由于添加负值没有意义，我决定采用最大值 0，并且对于 0 和 root.right 递归调用 root.left 类似 但现在我不知道如何处理具有负值的单个节点

Answer 1

...因为添加负值没有意义，所以我决定取最大值 0 并且递归调用

root.left

...

取最大值0并且返回值的想法很好。

现在我不知道如何处理具有负值的单个节点

问题不在于取 0 的最大值和递归的返回值，而在于下一个语句，您取

max[0]

的最大值以及包含

root.val

的路径总和。对于失败的情况，这意味着单个节点的负值永远无法从您在算法开始时初始化

max[0]

的 0 中获胜。但要意识到这个初始化值 0 并不对应于任何现实路径。

修正很简单：不要用 0 初始化

max[0]

，而是用极端负值初始化：

        int[] max = {Integer.MIN_VALUE};

或具有 realistic 值，可以是

root.val

（表示仅包含该节点的路径）：

        int[] max = {root.val};

当预期为负值时，两者都会使代码产生正确的值。