返回信息流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.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
下面是LZ的解法，但是超时了
public class Solution
{
int sum = Integer.MIN_VALUE;
int i = 0;
public int maxPathSum(TreeNode root)
{
dfs(root);
return sum;
}
public void dfs(TreeNode root)
{
if(root == null)
return;
int value = root.val;
if(i == 0)
{
sum = value;
//System.out.println(sum);
}
else
{
//System.out.println(value);
int max = value > sum + value? value : sum + value;
//System.out.println(max);
sum = max > sum ? max : sum;
//System.out.println(sum);
}
i++;
if(root.left != null)
dfs(root.left);
if(root.right != null)
dfs(root.right);
}
}
貌似一般的情况都能过，各位大神给点建议。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #88439同步于 2015/12/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
LeetCode的124题 Binary Tree Maximum Path Sum
sun111
2015/12/2镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
楼主的算法是有问题的吧 sum不能保证是连续的路径
正解是：对于以u为根的子树，求出子树节点中到u的最长两条路径。对于每个节点分别计算，求和找最大值就可以。上面两步可以用一个dfs就可以求出。o(N)的复杂度
dp[p]为从p节点开始的Maximum Path Sum，dp[p]=max(p.val,p.val+max(dp[left],dp[right]) p为父节点，left，right为左右孩子，初始化叶子节点dp[leaf]=leaf.val ,最后遍历每个节点的dp值 取最大的。