注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex124 Binary Tree Maximum Path Sum  

2015-05-27 23:06:52|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
求树的最大路径

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

题目说的是起点和重点都是任意的。本来比较简单的一道递归题目,开始思路也是对的,不知道脑袋哪儿被砸了,想着从底层上升的时候去改变current->val,从而计算最大值。
递归过程是这样的
求左子树内部的最大路劲和
求右子树内部的最大路径和,最后和left比较保存在maxValue里面
同时需要求一条路径跨越左树和右树的路径
最后退出root的时候和maxValue比较

这才是比较清晰的思路,当时真实脑袋被坑砸了~~~

class Solution {
public:
int maxValue = INT_MIN;
int maxPathSum(TreeNode* root) {
if (root == NULL)
return 0;
int result= traverse(root);
return result > maxValue ? result : maxValue;
}
int myMax(int a,int b)
{
return a > b ? a : b;
}
int myMin(int a, int b)
{
return a > b ? b : a;
}
int traverse(TreeNode* current)
{
//开始的时候我就是这个思路,子树内部的和子树外部的
//但是写程序的时候脑洞打开,居然想着用current->val来代替 最大sum
//然后就2B了,多么简单的一个题 而且我连小于0的情况都考虑了
//最后居然2B了~~~~~
if (current == NULL)
return 0;
int value = current->val;
int leftMax = 0;
int rightMax = 0;
if (current->left != NULL)
{
leftMax = traverse(current->left);
if (leftMax > 0)
{
value += leftMax; //只有左边大于0的时候才加进来
}
}
//同理对于右子树一样
if (current->right != NULL)
{
rightMax = traverse(current->right);
if (rightMax > 0)
{
value += rightMax;
}
}
if (value > maxValue)
maxValue = value; //这个其实是每次更新子树内部的最大值

//因为最后只有一条路径
//最后返回的要用到其他子树的更新上面去
return myMax(current->val,myMax(leftMax+current->val,rightMax+current->val));

}
};



  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017