前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode之Binary Tree Maximum Path Sum

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与子节点的第二个数比较,得到最大的一个数就等于当前的第二个数了。语言描述得可能有点混乱,下面直接上代码吧。

代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档