c********t
发帖数: 5706 | 1 响应号召，发中文题
二叉树求两结点间最大路径问题已经有很好解法。
现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
比如：
3
/
4
/ \
1 2
结果为10
请问有什么好的解法？
我有一个笨解法，指数时间复杂度，为了不影响大家做题，会在跟帖贴出。 |
p*****2
发帖数: 21240 | 2
感觉把从root到current node的sum传进来就可以了吧？
【在 c********t 的大作中提到】
: 响应号召，发中文题
: 二叉树求两结点间最大路径问题已经有很好解法。
: 现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
: 比如：
: 3
: /
: 4
: / \
: 1 2
: 结果为10
|
c********t
发帖数: 5706 | 3 似乎可以，如何传？用一个hashmap传？
【在 p*****2 的大作中提到】
:
: 感觉把从root到current node的sum传进来就可以了吧？
|
c********t
发帖数: 5706 | 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 的大作中提到】
: 响应号召，发中文题
: 二叉树求两结点间最大路径问题已经有很好解法。
: 现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
: 比如：
: 3
: /
: 4
: / \
: 1 2
: 结果为10
|
p*****2
发帖数: 21240 | 5
当函数的参数传进来
【在 c********t 的大作中提到】
: 似乎可以，如何传？用一个hashmap传？
|
c********t
发帖数: 5706 | 6 牛，已照你的解决，多谢
【在 p*****2 的大作中提到】
:
: 当函数的参数传进来
|
b***m
发帖数: 5987 | 7 嗯，这个变体应该不难解决。
【在 c********t 的大作中提到】
: 牛，已照你的解决，多谢
|
m*****k
发帖数: 731 | 8 两结点间最大路径问题与节点值有关么？
【在 c********t 的大作中提到】
: 响应号召，发中文题
: 二叉树求两结点间最大路径问题已经有很好解法。
: 现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
: 比如：
: 3
: /
: 4
: / \
: 1 2
: 结果为10
|
q****m
发帖数: 177 | 9 这是面试碰到的题目吗
【在 c********t 的大作中提到】
: 响应号召，发中文题
: 二叉树求两结点间最大路径问题已经有很好解法。
: 现在有一个变体题，两点间最大路径必须要加上共同祖先到root这段。
: 比如：
: 3
: /
: 4
: / \
: 1 2
: 结果为10
|
