LeetCode 124.二叉树最大路径和

Question

我正在尝试解决LeetCode问题124。二叉树最大路径和：

二叉树中的

路径是一个节点序列，其中序列中的每对相邻节点都有一条连接它们的边。一个节点只能在序列中出现最多一次。注意，路径不需要经过根。

路径的

路径总和是路径中节点值的总和。

给定二叉树的

root

，

返回任何非空路径的最大路径总和。

示例1：

输入： root = [1,2,3]

输出： 6
解释： 最优路径为 2 -> 1 -> 3

，路径总和为 

2 + 1 + 3 = 6

。

这是我的代码：

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

对于输入

[-3]

（这是一棵只有一个节点的树，值为-3），我的代码返回0，但预期的答案是-3。

如何解释这个特定的测试用例？

我只是取最大值 0 和递归调用来折扣负节点值。

由于添加负值没有意义，我决定取最大值 0 和递归调用

root.left

，类似地对于 0 和 

root.right

。

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

我应该如何调整我的代码以涵盖此类情况？

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}; 当预期为负值时，两者都会使代码产生正确的值。