p*******3
发帖数: 51 | 1 刚刚电面完，面试官感觉是个欧洲大叔，大叔人很好，我那题回答得是一路磕磕碰碰，
基础问题也回答得不好，大叔还是一直给提示，并且超时了还让我问问题，据说狗家很
多面试官时间一到直接挂电话。。。
题目是leetcode上BinaryTreeMaximumPathSum的变形题，path里不能有直接相接的node。
希望对大家有帮助～ |
s******x
发帖数: 417 | 2 "path里不能有直接相接的node"
如果一个树是 4
/\
3 5
最大值就是 3+5 = 8？ |
p*******3
发帖数: 51 | 3 对~~
【在 s******x 的大作中提到】
: "path里不能有直接相接的node"
: 如果一个树是 4
: /\
: 3 5
: 最大值就是 3+5 = 8？
|
b********a
发帖数: 70 | 4 求各位发面经的时候说详细点好么？
一个path总是要连在一起的 你说path里的点不能直接连是说在正常的path里每隔一个
或多个node相加么？
这题出的真怪异啊 感觉是想让面试者把原题的算法稍做修改? |
p*******3
发帖数: 51 | 5 对，path还是要连接的，就是node不能相邻。面试官问题刚说完，我就感觉他应该也刷
过题了，哈哈
【在 b********a 的大作中提到】
: 求各位发面经的时候说详细点好么？
: 一个path总是要连在一起的 你说path里的点不能直接连是说在正常的path里每隔一个
: 或多个node相加么？
: 这题出的真怪异啊 感觉是想让面试者把原题的算法稍做修改?
|
z****0
发帖数: 4413 | 6 mark
node。
【在 p*******3 的大作中提到】
: 刚刚电面完，面试官感觉是个欧洲大叔，大叔人很好，我那题回答得是一路磕磕碰碰，
: 基础问题也回答得不好，大叔还是一直给提示，并且超时了还让我问问题，据说狗家很
: 多面试官时间一到直接挂电话。。。
: 题目是leetcode上BinaryTreeMaximumPathSum的变形题，path里不能有直接相接的node。
: 希望对大家有帮助～
|
c******n
发帖数: 4965 | 7 还是不明白， 能不能再给个例子？
你又说path 要连， 又说node 不连， path 不就是 node 连成的么？。。。。。。ft
我自己都晕了
【在 p*******3 的大作中提到】
: 对，path还是要连接的，就是node不能相邻。面试官问题刚说完，我就感觉他应该也刷
: 过题了，哈哈
|
i*******a
发帖数: 61 | 8 能说说思路嘛？是像这个array这样的maintain two sums incl and excl where incl
= Max sum including the previous element and excl = Max sum excluding the
previous
element.http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/ |
p*******3
发帖数: 51 | 9 呃，看来我描述得确实不太清楚，罪过罪过。。。
这么想吧，你还是找pathsum，但是这个用来求和的node不能相邻。例如说
1
/ \
2 3
/ \
1 8
你就可以选择8-2-1-3这条path，求和用8+3=11最大。
ft
【在 c******n 的大作中提到】
: 还是不明白， 能不能再给个例子？
: 你又说path 要连， 又说node 不连， path 不就是 node 连成的么？。。。。。。ft
: 我自己都晕了
|
p*******3
发帖数: 51 | 10 嗯，楼主很弱也没有答得很好，请各位大神指教～～
不过我觉得基本思路应该是leetcode那道题的思路但是每次求和的时候要跳过子结点。
incl
【在 i*******a 的大作中提到】
: 能说说思路嘛？是像这个array这样的maintain two sums incl and excl where incl
: = Max sum including the previous element and excl = Max sum excluding the
: previous
: element.http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
|
