c*********y
发帖数: 135 | 1 Binary Tree Maximum Path Sum
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～ |
j*****8
发帖数: 3635 | 2 store two max sums for every node,
one is the max sum for the path ending at that node with length 2; the other
is for all other lengths
刚才大号时随便想的，没有验证过。。
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
e********2
发帖数: 495 | 3 dp
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
c*********y
发帖数: 135 | 4 不懂， 能否详细解释一下。
other
【在 j*****8 的大作中提到】
: store two max sums for every node,
: one is the max sum for the path ending at that node with length 2; the other
: is for all other lengths
: 刚才大号时随便想的，没有验证过。。
|
k****r
发帖数: 807 | 5 I finished one following the similar idea in LC maxPathInTree. Use a wrapper
to return the current closeMax and farMax of each subTree. At the same time
, calculate the currentMaxPathSum:
public static int maxPath = Integer.MIN_VALUE;
public static int maxJumpPathinTree(TreeNode root) {
maxJumpPathHelper(root);
return maxPath;
}
public static SumWrapper maxJumpPathHelper(TreeNode root) {
if (root == null) return new SumWrapper(0, 0);
SumWrapper left = maxJumpPathHelper(root.left);
SumWrapper right = maxJumpPathHelper(root.right);
int valWithRoot = root.val;
if (left.far > 0) valWithRoot += left.far;
if (right.far > 0) valWithRoot += right.far;
int valWithoutRoot = Math.max(left.far, left.close);
if (Math.max(right.far, right.close) > 0) valWithoutRoot += Math.max
(right.far, right.close);
maxPath = Math.max(maxPath, Math.max(valWithRoot, valWithoutRoot));
int close = root.val;
if (Math.max(left.far, right.far) > 0) close += Math.max(left.far,
right.far);
int far = Math.max(Math.max(left.far, left.close), Math.max(right.
far, right.close));
return new SumWrapper(close, far);
}
class SumWrapper {
int close;
int far;
SumWrapper (int close, int far) {
this.close = close;
this.far = far;
}
} |
d******b
发帖数: 73 | 6 其实我不大明白 你所谓的不相邻，不过，节点只有相邻 和 不相邻 两种情况，如果你
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary） |
l*3
发帖数: 2279 | 7 妈的看得我十分愤怒。
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
l*3
发帖数: 2279 | 8 妈的看得我十分愤怒。
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
c*********y
发帖数: 135 | 9 哦没解释好。以下是leetode原题：
leetcode Binary Tree Maximum Path Sum:
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.
对于面经我的理解是在leetcode这道题基础之上找最大，但是不能是parent child 关
系的相邻。 |
k****r
发帖数: 807 | 10 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
lz给这个例子结果就是5吧？
【在 c*********y 的大作中提到】
: 哦没解释好。以下是leetode原题：
: leetcode Binary Tree Maximum Path Sum:
: 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
: / \
|
|
|
c*********y
发帖数: 135 | 11 对呀对呀:)
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
|
v****o
发帖数: 11 | 12 怎么就变成5了
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
|
t***t
发帖数: 6066 | |
b*******w
发帖数: 56 | 14 Is the node value positive? |
c*********y
发帖数: 135 | 15 Binary Tree Maximum Path Sum
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～ |
j*****8
发帖数: 3635 | 16 store two max sums for every node,
one is the max sum for the path ending at that node with length 2; the other
is for all other lengths
刚才大号时随便想的，没有验证过。。
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
e********2
发帖数: 495 | 17 dp
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
|
c*********y
发帖数: 135 | 18 不懂， 能否详细解释一下。
other
【在 j*****8 的大作中提到】
: store two max sums for every node,
: one is the max sum for the path ending at that node with length 2; the other
: is for all other lengths
: 刚才大号时随便想的，没有验证过。。
|
k****r
发帖数: 807 | 19 I finished one following the similar idea in LC maxPathInTree. Use a wrapper
to return the current closeMax and farMax of each subTree. At the same time
, calculate the currentMaxPathSum:
public static int maxPath = Integer.MIN_VALUE;
public static int maxJumpPathinTree(TreeNode root) {
maxJumpPathHelper(root);
return maxPath;
}
public static SumWrapper maxJumpPathHelper(TreeNode root) {
if (root == null) return new SumWrapper(0, 0);
SumWrapper left = maxJumpPathHelper(root.left);
SumWrapper right = maxJumpPathHelper(root.right);
int valWithRoot = root.val;
if (left.far > 0) valWithRoot += left.far;
if (right.far > 0) valWithRoot += right.far;
int valWithoutRoot = Math.max(left.far, left.close);
if (Math.max(right.far, right.close) > 0) valWithoutRoot += Math.max
(right.far, right.close);
maxPath = Math.max(maxPath, Math.max(valWithRoot, valWithoutRoot));
int close = root.val;
if (Math.max(left.far, right.far) > 0) close += Math.max(left.far,
right.far);
int far = Math.max(Math.max(left.far, left.close), Math.max(right.
far, right.close));
return new SumWrapper(close, far);
}
class SumWrapper {
int close;
int far;
SumWrapper (int close, int far) {
this.close = close;
this.far = far;
}
} |
d******b
发帖数: 73 | 20 其实我不大明白 你所谓的不相邻，不过，节点只有相邻 和 不相邻 两种情况，如果你
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary） |
|
|
c*********y
发帖数: 135 | 21 哦没解释好。以下是leetode原题：
leetcode Binary Tree Maximum Path Sum:
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.
对于面经我的理解是在leetcode这道题基础之上找最大，但是不能是parent child 关
系的相邻。 |
k****r
发帖数: 807 | 22 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
lz给这个例子结果就是5吧？
【在 c*********y 的大作中提到】
: 哦没解释好。以下是leetode原题：
: leetcode Binary Tree Maximum Path Sum:
: 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
: / \
|
c*********y
发帖数: 135 | 23 对呀对呀:)
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
|
v****o
发帖数: 11 | 24 怎么就变成5了
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
|
t***t
发帖数: 6066 | |
b*******w
发帖数: 56 | 26 Is the node value positive? |
c*********y
发帖数: 135 | 27 不是，整数，可正负零。
【在 b*******w 的大作中提到】
: Is the node value positive?
|
J*****e
发帖数: 158 | 28 没明白题目，就是这个path和之前定义的tree的path没有任何联系了？实际只是找一系
列的节点而且节点不能“相邻”？把树对应换成数组就是类似house robber那题？
【在 c*********y 的大作中提到】
: 哦没解释好。以下是leetode原题：
: leetcode Binary Tree Maximum Path Sum:
: 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
: / \
|
c*********y
发帖数: 135 | 29 对呀，path定义和leetcode一样，可以在任何位置起，任何位置止，但是不能有相邻的
node组成。挺像house robber的。
我其实已经会做了。。。。。
请大家忽略这道题吧。
【在 J*****e 的大作中提到】
: 没明白题目，就是这个path和之前定义的tree的path没有任何联系了？实际只是找一系
: 列的节点而且节点不能“相邻”？把树对应换成数组就是类似house robber那题？
|
J*****e
发帖数: 158 | 30 那么说说你的思路吧
我觉得如果用level order traversal转成array，然后用类似house robber的dp或许可以
【在 c*********y 的大作中提到】
: 对呀，path定义和leetcode一样，可以在任何位置起，任何位置止，但是不能有相邻的
: node组成。挺像house robber的。
: 我其实已经会做了。。。。。
: 请大家忽略这道题吧。
|
|
|
c*********y
发帖数: 135 | 31 这是我写的代码。大体测了下。
class Solution {
public:
int helper(TreeNode * root, int &global_max){
//this returns max value of the subtree root
//global_max is the results value we are looking for
if(root==NULL)return 0;
int left = max(0,helper(root->left, global_max)); // the key point
is here that we make the return value always larger than or equal to zero.
int right = max(0,helper(root->right, global_max));
int left_next = root->left?max(helper(root->left->right, global_max)
,helper(root->left->left, global_max)):0;
left_next= max(0,left_next);
int right_next = root->right?max(helper(root->right->right, global_
max),helper(root->right->left, global_max)):0;
right_next= max(0,right_next);
global_max = max(global_max, left + right);
global_max = max(global_max, root->val+ left_next+right_next);
return max(max(right_next, left_next)+root->val, max(left,right));
}
int maxPathSum(TreeNode* root) {
int global_max = INT_MIN;
helper(root, global_max);
return global_max;
}
};
可以
【在 J*****e 的大作中提到】
: 那么说说你的思路吧
: 我觉得如果用level order traversal转成array，然后用类似house robber的dp或许可以
|
p******n
发帖数: 185 | 32 考虑起点和终点node为树中任意位置node(但满足相邻node不同时选），不止同一高度
最多选一个node的情况.代码如下
class Solver{
public:
int maxPathSumNoAdj(TreeNode* root){
int maxsumBelow=0, maxsum=0, maxPath=0;
maxPathSumNoAdj(root, maxsumBelow, maxsum, maxPath);
return maxPath;
}
void maxPathSumNoAdj(TreeNode* root, int& maxsumBelow, int& maxsum,
int& maxPath){
if(root->left==NULL && root->right==NULL){
maxsumBelow=0;
maxsum= (root->val>0)? root->val : 0;
maxPath= max(maxPath, maxsum);
return;
}
int maxsumBelowLeft=0, maxsumLeft=0;
if(root->left!=NULL)
maxPathSumNoAdj(root->left, maxsumBelowLeft,maxsumLeft,maxPath);
int maxsumBelowRight=0, maxsumRight=0;
if(root->right!=NULL)
maxPathSumNoAdj(root->right, maxsumBelowRight, maxsumRight,maxPath);
maxsumBelow=max(maxsumLeft, maxsumRight);
maxsum= max(maxsumBelow,
max(maxsumBelowLeft, maxsumBelowRight)+((root->val>0)? root->val:0) );
int cmaxPath= max(maxsumLeft+maxsumRight, maxsumBelowLeft+maxsumBelowRight+(
(root->val>0)? root->val:0));
maxPath= max(maxsum, cmaxPath);
}
};
【在 c*********y 的大作中提到】
: 哦没解释好。以下是leetode原题：
: leetcode Binary Tree Maximum Path Sum:
: 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
: / \
|
T*****n
发帖数: 82 | 33 public class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxSum(root);
return max;
}
private int maxSum(TreeNode root){
if(root == null){
return 0;
}
int left = maxSum(root.left);
int right = maxSum(root.right);
max = Math.max(max, root.val + left + right);
int ret = Math.max(root.val + left, root.val + right);
return ret > 0 ? ret : 0;
}
} |
