leetcode124 -- Binary Tree Maximum Path Sum (Hard)

leetcode124 -- Binary Tree Maximum Path Sum (Hard)

题目


Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

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


解答


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

是在网上看的大神的解答, 大致的意思是说定义一个helper函数, 如果它是个叶子节点的话,就把它上面的值给返回出来,如果它不是叶子节点的话,比如

        1
    /       \
2               3        

就返回1+21+31中的较大的那一个,因为left和right都可能是0, 也有可能是负数.

然后 res是用来保存最后的最大的和的,当走到一个节点的时候,如果左边的最大和是负的,我们就不加它了,即是0,如果它是正的,我们希望加上它,右边也是同样的道理,所以这时候左子树对当前的最大和的贡献 就是

max(0, helper(node>left, res)), 右子树的贡献就是max(0, helper(node->right, res))

所以走到当前节点的时候的最大值应该是res = max(res, left+right+node->val), 但是这个并不是helper这个函数要返回的对象,它要返回的是max(left, right)+node->val.

备注理解

实际上,上面定义的helper函数是为了返回以该节点为终点或者以该结点为起点的所有path的最大和(当然包括该节点自己)

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦