LeetCode日记–124. Binary Tree Maximum Path Sum

发布于 2020-10-10  108 次阅读


碎碎念:就。。没啥好碎碎念的,下午的课是真的难受,每次都困一下午。

题目如下:

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]
  -10
   / \
  9  20
    /  \
   15   7
Output: 42

解释:

路径可以不经过根节点,但是不能有回头路,只能一直走下去。因此在Example2中,输出就是15->20->7,最终结果是42.

思路:

这题的思路从递归的角度来说非常简单,就是一路递归,然后把递归返回的左右节点值和本层节点相加。

但是我们注意路径的定义中一个很重要的点,就是不能走回头路,也就是说一个节点往上走时只有一个分支对值进行了贡献。比如说Example2中,当15->20后,若要形成到 -10 节点的路径,则其不能经过 7 节点。因此我们返回给父节点的返回值应该是左右子树中路径的最大贡献值。

同时,如果某个分支的贡献是负数,那么我们就抛弃这个分支,把这个分支看做0,不计入路径中。

细节:

我已开始的思路都与上面的思路相近,代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        if(root.left==null&&root.left==null)
            return root.val;
        return helper(root);
    }
    public int helper(TreeNode root){
        if(root==null)
            return 0;
        int res = 0;
        res += helper(root.left) > 0 ? helper(root.left):0;
        if(root.val+res>0)
            res+=root.val;
        else{
            if(root.right==null&&root.left!=null)
                return Math.max(root.val,root.left.val);
            else
            return helper(root.right);
        }
        res += helper(root.right) > 0 ? helper(root.right):0;
        return res;
    }
}

但是一直出错,这是为什么呢?因为我忽略了一个很重要的事情--最终结果路径不一定经过root节点。所以我返回root是不对的。这时我们需要维护一个全局变量maxSum,记录到目前为止得到的最大路径。

但是又一个问题来了,maxSum的初值应该是多少呢?大部分人(包括我)应该都是先赋值为0吧,但是再仔细想想,如果所有节点都是负数怎么办呢,这时的返回值会是什么呢?显然,这时候返回的是0,一个错误的答案。因此,我们要将全局变量的初值赋值为 Integer.MIN_VALUE 。

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    public int helper(TreeNode root){
        if(root==null)
            return 0;
        // int thisNodeSum = 0;
        int leftSum = Math.max(0,helper(root.left));
        int rightSum = Math.max(0,helper(root.right));;
        // int leftSum = helper(root.left) > 0 ? helper(root.left):0;
        // int rightSum = helper(root.right) > 0 ? helper(root.right):0;
        int thisNodeSum= leftSum + rightSum + root.val;
        maxSum = Math.max(maxSum,thisNodeSum);
        // 返回值是当前节点的贡献值,因为返回上方父节点时只有上中左,上中右两个可能性
        return root.val + Math.max(leftSum,rightSum);
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)