问一道google面经# JobHunting - 待字闺中
c*y
1 楼
Binary Tree Maximum Path Sum
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～
j*8
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才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
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
3 楼
dp
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
c*y
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
: 刚才大号时随便想的，没有验证过。。
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
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;
}
}
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
6 楼
其实我不大明白 你所谓的不相邻，不过，节点只有相邻 和 不相邻 两种情况，如果你
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary）
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary）
l*3
7 楼
妈的看得我十分愤怒。
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
l*3
8 楼
妈的看得我十分愤怒。
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
1. 自己问题，题都不说清楚，说了一个题目名称谁特么知道你具体题目细节是什么意
思？
2. binary tree什么叫不相邻的node？binary tree里有这个概念？父子节点就父子节
点，左右子树互为兄弟就说互为兄弟，相邻不相邻是你么什么屁玩意？
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
c*y
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 关
系的相邻。
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
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
: / \
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
11 楼
对呀对呀:)
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
v*o
12 楼
怎么就变成5了
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
t*t
13 楼
做android不是挺好么？
b*w
14 楼
Is the node value positive?
c*y
15 楼
Binary Tree Maximum Path Sum
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～
但是需要是不相邻的node才可以算。
写了很久就是写不对。请指教啊。多谢！～
j*8
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才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
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
17 楼
dp
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
【在 c*********y 的大作中提到】
: Binary Tree Maximum Path Sum
: 但是需要是不相邻的node才可以算。
: 写了很久就是写不对。请指教啊。多谢！～
c*y
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
: 刚才大号时随便想的，没有验证过。。
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
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;
}
}
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
20 楼
其实我不大明白 你所谓的不相邻，不过，节点只有相邻 和 不相邻 两种情况，如果你
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary）
认为 相邻 和 不相邻 关系 翻转，说白了 就是 另一种 形态的 Tree Maximum Path
Sum（不是 Binary）
c*y
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 关
系的相邻。
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
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
: / \
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
23 楼
对呀对呀:)
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
v*o
24 楼
怎么就变成5了
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
【在 k****r 的大作中提到】
: 我怎么觉得不相邻挺好理解的，不相邻不就是path中的相邻item不存在父子关系呗：）
: lz给这个例子结果就是5吧？
t*t
25 楼
做android不是挺好么？
b*w
26 楼
Is the node value positive?
c*y
27 楼
不是，整数，可正负零。
【在 b*******w 的大作中提到】
: Is the node value positive?
【在 b*******w 的大作中提到】
: Is the node value positive?
J*e
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
: / \
列的节点而且节点不能“相邻”？把树对应换成数组就是类似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
29 楼
对呀，path定义和leetcode一样，可以在任何位置起，任何位置止，但是不能有相邻的
node组成。挺像house robber的。
我其实已经会做了。。。。。
请大家忽略这道题吧。
【在 J*****e 的大作中提到】
: 没明白题目，就是这个path和之前定义的tree的path没有任何联系了？实际只是找一系
: 列的节点而且节点不能“相邻”？把树对应换成数组就是类似house robber那题？
node组成。挺像house robber的。
我其实已经会做了。。。。。
请大家忽略这道题吧。
【在 J*****e 的大作中提到】
: 没明白题目，就是这个path和之前定义的tree的path没有任何联系了？实际只是找一系
: 列的节点而且节点不能“相邻”？把树对应换成数组就是类似house robber那题？
J*e
30 楼
那么说说你的思路吧
我觉得如果用level order traversal转成array，然后用类似house robber的dp或许可以
【在 c*********y 的大作中提到】
: 对呀，path定义和leetcode一样，可以在任何位置起，任何位置止，但是不能有相邻的
: node组成。挺像house robber的。
: 我其实已经会做了。。。。。
: 请大家忽略这道题吧。
我觉得如果用level order traversal转成array，然后用类似house robber的dp或许可以
【在 c*********y 的大作中提到】
: 对呀，path定义和leetcode一样，可以在任何位置起，任何位置止，但是不能有相邻的
: node组成。挺像house robber的。
: 我其实已经会做了。。。。。
: 请大家忽略这道题吧。
c*y
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或许可以
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
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
: / \
最多选一个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
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;
}
}
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;
}
}
相关阅读
996向少儿发展，狼性文化蔓延工作岗位上，每个人都是带着面具的机器！请问微软65级的offer RSU和sign on bonus是个什么range?Chicago Job Opportunities亚马逊的冷冻期现在面试的这些人，差距真的太大了求职小经验国内eda马公月薪3万美刀 (转载)喜见drive.ai倒闭硅谷A轮公司招深圳研发中心技术负责人Boston offer请问这个职位是什么Level?Amazon Selection and Catalog Systems (ASCS) 怎么羊烙印再下一城 (转载)onsite 第二天一早hr发来这么个email,是好是坏？没见过对人爱答不理的烙印【工作机会】Machine Learning & NLP Engineer --Palo AltoPatreon这个小公司有没有人了解？Amazon有没有FLG那样的每年只能面一次的policy？[ZZ]同事太弱又划水 我该和老板说吗？