LeetCode之Binary Tree Maximum Path Sum

forrestlin

发布于 2018-05-24 11:04:53

4740

发布于 2018-05-24 11:04:53

文章被收录于专栏：蜉蝣禅修之道

题目：

Given a 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 does not need to go through the root.

理解：在二叉树中找一条最大sum的路径，而该路径的两头可以是任意的节点，不一定是root。要是经过root的最大path很简单，但现在是任意两点的path啊，只好画个图分析分析了，如下图所示：

我这里给每个节点加上两个信息，第一个是可以往上传递的最大sum，也就是这个sum的产生肯定是一条直的path，这个sum>=node->val，第二个信息是以当前节点为根节点时能得到的最大sum，这里允许path可以拐弯，显然第二个数是大于等于第一个数，最后返回根节点的第二个数就行。

首先对于叶结点，两个数肯定都等于节点的value，而对于非叶结点，找出最大子节点的第一个数a，假如a大于0，那么当前节点的第一个数就等于value+a，否则就等于value，而对于第二个数就，首先求得当前节点的value+大于0的子节点的第一个数，假设这个结果为b，然后b与子节点的第二个数比较，得到最大的一个数就等于当前的第二个数了。语言描述得可能有点混乱，下面直接上代码吧。

class Solution {
public:
    void maxPathSum(TreeNode* root,int& leafNum,int& maxNum){
        if(!root->left&&!root->right){
            leafNum=root->val;
            maxNum=root->val;
            return;
        }
        int leftLeaf=INT_MIN,leftMax=INT_MIN;
        if(root->left){
            maxPathSum(root->left,leftLeaf,leftMax);
        }
        int rightLeaf=INT_MIN,rightMax=INT_MIN;
        if(root->right){
            maxPathSum(root->right,rightLeaf,rightMax);
        }
        int childLeaf=leftLeaf>rightLeaf?leftLeaf:rightLeaf;
        leafNum=root->val;
        if(childLeaf>0)
            leafNum+=childLeaf;
        int childMax=leftMax>rightMax?leftMax:rightMax;
        int sum=root->val;
        if(leftLeaf>0)
            sum+=leftLeaf;
        if(rightLeaf>0)
            sum+=rightLeaf;
        if(sum>childMax)
            maxNum=sum;
        else
            maxNum=childMax;
        return;
    }
    int maxPathSum(TreeNode* root) {
        if(!root)
            return 0;
        int leafNum=0,maxNum=0;
        maxPathSum(root,leafNum,maxNum);
        return maxNum;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016年01月27日，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树