a****x
发帖数: 89 | 1 网上搜到的都没有考虑negative的情况，比如一个tree只有一个node，这个node的值
是negative。
下面是我自己的答案，已经pass OJ：
class LocalResult
{
int localMaxPathSum; // local max path sum
int localSubPathSum; // either root, or root+left, or root+right
public LocalResult(int maxPathSum, int subPathSum)
{
this.localMaxPathSum = maxPathSum;
this.localSubPathSum = subPathSum;
}
}
public class binaryTreeMaxPathSum {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public int maxPathSum(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
LocalResult result = maxPathSumLocal(root);
return result.localMaxPathSum > result.localSubPathSum ? result.
localMaxPathSum : result.localSubPathSum;
}
private int maxOfThree(int a, int b, int c)
{
int result = a;
if(b > result)
result = b;
if(c > result)
result = c;
return result;
}
private LocalResult maxPathSumLocal(TreeNode root)
{
if(root == null)
{
return null;
}
LocalResult left = maxPathSumLocal(root.left);
LocalResult right = maxPathSumLocal(root.right);
int localMaxPathSum = root.val;
int localSubPathSum = root.val;
if(left != null && left.localSubPathSum > 0)
localMaxPathSum += left.localSubPathSum;
if(right != null && right.localSubPathSum > 0)
localMaxPathSum += right.localSubPathSum;
if(left != null && right != null)
{
localMaxPathSum = maxOfThree(localMaxPathSum, left.
localMaxPathSum, right.localMaxPathSum);
localSubPathSum = maxOfThree(root.val, root.val + left.
localSubPathSum, root.val + right.localSubPathSum);
}
else if(left != null)
{
localMaxPathSum = localMaxPathSum > left.localMaxPathSum ?
localMaxPathSum : left.localMaxPathSum;
localSubPathSum = localSubPathSum > root.val + left.
localSubPathSum ? localSubPathSum : root.val + left.localSubPathSum;
}
else if(right != null)
{
localMaxPathSum = localMaxPathSum > right.localMaxPathSum ?
localMaxPathSum : right.localMaxPathSum;
localSubPathSum = localSubPathSum > root.val + right.
localSubPathSum ? localSubPathSum : root.val + right.localSubPathSum;
}
return new LocalResult(localMaxPathSum, localSubPathSum);
}
}
觉得有些臃肿，主要是return null而不是0当碰到leave时，所以得判断返回的结果是
不是null。有更简洁的吗？ | h****n
发帖数: 1093 | 2 面试写成这样子就挂了
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res;
int g;
res = helper(root, g);
return res;
}
int helper(TreeNode * root, int & g)
{
if(!root)
{
g = 0;
return 0;
}
int leftG, rightG;
int maxSum = INT_MIN;
int leftMax = helper(root->left, leftG);
int rightMax = helper(root->right, rightG);
if(!root->left&&!root->right)
maxSum = root->val;
else if(!root->left)
maxSum = max(rightMax, root->val + leftG + rightG);
else if(!root->right)
maxSum = max(leftMax, root->val + leftG + rightG);
else maxSum = max(max(leftMax,rightMax),root->val + leftG + rightG);
g = max(0, root->val+max(leftG, rightG));
return maxSum;
}
}; | f*****7
发帖数: 92 | 3 贴个我的，divide-and-conquer
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int globalMax = INT_MIN;
maxPathSum(root, globalMax);
return globalMax;
}
//return the max path sum INCLUDES root node
//which is the key to this elegant divide-and-conquer solution
int maxPathSum(TreeNode* root, int& globalMax)
{
if (NULL == root)
{
return 0;
}
else
{
//max sum of left leg
int leftSum = maxPathSum(root->left, globalMax);
//max sum of right leg
int rightSum = maxPathSum(root->right, globalMax);
//conquer stage
//max sum cross the root, 4 possibilities
int crossSum = max(root->val, max(leftSum + root->val, max(
rightSum + root->val, leftSum + root->val + rightSum)));
//update global variable if nec.
if (crossSum > globalMax)
{
globalMax = crossSum;
}
//return the max path sum INCLUDES root node
return max(root->val, max(root->val + leftSum, root->val +
rightSum));
}
}
}; | l*******b
发帖数: 2586 | 4 int maxPathSum(Node *h) {
int m = h->val;
stack ss;
stack ms;
Node *ret = NULL;
while(h || !ss.empty()) {
if(h) {
ss.push(h);
h = h->l;
continue;
}
h = ss.top();
if(NULL == h->r || ret == h->r) {
int mr = 0, ml = 0;
if(h->r) { mr = max(ms.top(), 0); ms.pop();}
if(h->l) { ml = max(ms.top(), 0); ms.pop();}
m = max(m, h->val + mr + ml);
ms.push(h->val + max(mr, ml));
ret = h;
h = NULL;
ss.pop();
}
else
h = h->r;
}
return m;
}
后序遍历的写法 | l*******b
发帖数: 2586 | 5 int maxPathSII(Node *h) {
int m = h->val;
int res = helper(h, m);
return m;
}
int helper(Node *h, int &m) {
if(NULL == h) return 0;
int ml = max(helper(h->l, m), 0);
int mr = max(helper(h->r, m), 0);
m = max(m, h->val + mr + ml);
return h->val + max(mr, ml);
}
学习一下递归的写法。。 | a****x
发帖数: 89 | 6 多谢指教，仿照你的写了个java的，pass了：
private LocalResult maxPathSumLocal(TreeNode root)
{
if(root == null)
{
return new LocalResult(0,0);
}
LocalResult left = maxPathSumLocal(root.left);
LocalResult right = maxPathSumLocal(root.right);
int maxSoFar,leg;
if(root.left == null && root.right == null)
maxSoFar = root.val;
else if(root.left == null)
maxSoFar = maxOfTwo(right.maxSoFar, root.val + right.leg);
else if(root.right == null)
maxSoFar = maxOfTwo(left.maxSoFar, root.val + left.leg);
else
maxSoFar = maxOfThree(left.maxSoFar, right.maxSoFar, root.val +
left.leg + right.leg);
leg = maxOfThree(0,root.val + left.leg, root.val + right.leg);
return new LocalResult(maxSoFar, leg);
}
【在 h****n 的大作中提到】
: 面试写成这样子就挂了
: class Solution {
: public:
: int maxPathSum(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int res;
: int g;
:
: res = helper(root, g);
| d**e
发帖数: 6098 | 7 好像大家都要一个global max，这个有什么用吗？我觉得不要也没关系。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这里为什么要左右都加呢？这样不成为一条path吧。
【在 f*****7 的大作中提到】
: 贴个我的，divide-and-conquer
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
| P******r
发帖数: 842 | 8 和我的几乎一点不差。不知道还能不能有跟好一些的。
【在 f*****7 的大作中提到】
: 贴个我的，divide-and-conquer
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
| f*****7
发帖数: 92 | 9 这才是divide-and-conquer啊
一条path，可能全在左子树，可能全在右子树，也可能跨过root
跨过root的path，就有四种情况。
我这么写，每个子树的sum都是一条从子树的root开始的path，这样和root相连成一条
path。
你这么后序递归走几步，就发现leftSum和rightSum是root的“两条腿”
【在 d**e 的大作中提到】
: 好像大家都要一个global max，这个有什么用吗？我觉得不要也没关系。
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 这里为什么要左右都加呢？这样不成为一条path吧。
| i******e
发帖数: 273 | 10 20
/ \
-3 -5
/ \
3 8
/ \ \
-2 -1 10
/ /
6 -7
这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
按照你的程序
在根节点 20： maxSum = max(max(helper(-3, leftG), helpfer(-5， rightG)， 20
+ leftG + rightG);
因为leftG包含了以结点3为子树根节点的一条路径（6 -> -1 -> 3 -> -3 -> 8 -> 10
）. 这条路径不能和根节点20一起构成一条新的路径. 所以得出的解是最大和（20 +
23 = 43）， 但是却不是一条有效路径。
请大家帮忙看一下是不是我哪算的有问题？ 谢谢。
【在 h****n 的大作中提到】
: 面试写成这样子就挂了
: class Solution {
: public:
: int maxPathSum(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int res;
: int g;
:
: res = helper(root, g);
| i******e
发帖数: 273 | 11 不好意思是我算错了
【在 i******e 的大作中提到】
: 20
: / \
: -3 -5
: / \
: 3 8
: / \ \
: -2 -1 10
: / /
: 6 -7
: 这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
|
|
