求二叉树最大路径和的变体题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求二叉树最大路径和的变体题

求二叉树最大路径和的变体题# JobHunting - 待字闺中

c*t2012-11-13 08:11

1 楼

响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。

p*22012-11-13 08:11

2 楼

感觉把从root到current node的sum传进来就可以了吧？

【在 c********t 的大作中提到】

: 响应号召，发中文题
: 二叉树求两结点间最大路径问题已经有很好解法。
: 现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
: 比如：
: 3
: /
: 4
: / \
: 1 2
: 结果为10

c*t2012-11-13 08:11

3 楼

似乎可以，如何传？用一个hashmap传？

【在 p*****2 的大作中提到】

:
: 感觉把从root到current node的sum传进来就可以了吧？

c*t2012-11-13 08:11

4 楼

我的笨办法,好像也没考虑负数。dfs求的是从结点到叶子的最大路径。
int dfs(BinNode root) {
if (root == null)
return 0;
if (root.left == null)
return root.value + dfs(root.right);
if (root.right == null)
return root.value + dfs(root.left);
return root.value + Math.max(dfs(root.left), dfs(root.right));
}
int maxpath(BinNode root) {
if (root == null)
return 0;
int p1 = dfs(root.left);
int p2 = dfs(root.right);
return Math.max(p1 + p2,
Math.max(maxpath(root.left), maxpath(root.right)))
+ root.value;
}

【在 c********t 的大作中提到】

p*22012-11-13 08:11

5 楼

当函数的参数传进来

【在 c********t 的大作中提到】

: 似乎可以，如何传？用一个hashmap传？

c*t2012-11-13 08:11

6 楼

牛，已照你的解决，多谢

【在 p*****2 的大作中提到】

:
: 当函数的参数传进来