124. Binary Tree Maximum Path Sum

  • 25.3%

https://leetcode.com/problems/binary-tree-maximum-path-sum/?tab=Description

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 must contain at least one node and does not need to go through the root.

1
2
3
4
5
6
7
For example:
Given the below binary tree,

1
/ \
2 3
Return 6.

面试360时遇到,核心提示,使用带参数的函数。

方法一:

[recommend for beginners]clean C++ implementation with detailed explanation

help函数,表征从root节点开始,至叶节点之间的最大value。

sum通过获取,help(root->left), help(root->right), 再加上root->val的和为sum,与先前的sum比较,进行更新。

其中,help(root->left)<=0时,此处应为0。

code 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
int sum;
public:
int maxPathSum(TreeNode* root) {
sum=INT_MIN;
help(root);
return sum;
}

/*** return the max-value-ended-at-root-node ***/
int help(TreeNode* root){
if(!root) return 0;
int left = max(0, help(root->left));
int right = max(0, help(root->right));
/*** key parts : embedding the max-value-find in the recursion process ***/
sum = max(sum, left+right+root->val);
/*** get the max-value-ended-at-root ***/
return max(left, right)+root->val;
}
};

code 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
int maxToRoot(TreeNode *root, int &re) {
if (!root) return 0;
int l = maxToRoot(root->left, re);
int r = maxToRoot(root->right, re);
if (l < 0) l = 0;
if (r < 0) r = 0;
if (l + r + root->val > re) re = l + r + root->val;
return root->val += max(l, r);
}
public:
int maxPathSum(TreeNode *root) {
int max = -2147483648;
maxToRoot(root, max);
return max;
}
};

code 3:

我自己的代码

逻辑还是很简单的,但是要考虑周全,不然ac不过去。

res表示最长路径的大小,然后在helper函数中,传的是地址。

helper中是树的先序遍历。root==NULL自不必说。helper函数返回当前节点出发至下面任意节点之间的最大的值得大小。当前的root对应的的值为cur,要考虑这个大小,就要考虑左节点出发的大小,右节点的大小,这时,更新下res的大小,通过当前节点的加上左右分支的节点的最大值,为cur_max去更新res的值。然后返回值呢,就是左节点右节点的最大值与0的最大值加上cur,因为返回值是通过当前节点的一条分支的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxPathSum(TreeNode* root) {
if(root==NULL) return 0;
int res = INT_MIN; // 初始值设置为INT_MIN,而不是0,否则负数会出错误结果。
helper(root, res);
return res;
}

int helper(TreeNode* root, int & res){
if(root==NULL)
return 0;
int cur = root->val;
int left = helper(root->left, res);
int right = helper(root->right, res);
int cur_max = max(left,0) + max(right, 0) + cur;
res = max(cur_max, res);
return max(max(left, right), 0)+cur;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
helper(root, res);
return res;
}

int helper(TreeNode* root, int & res){
if(!root)
return 0;
int left = helper(root->left, res);
int right = helper(root->right, res);
left = max(left, 0);
right = max(right, 0);
res = max(left+right+root->val, res);
return max(left, right)+root->val;
}
};

方法二:

这种方法与上一种逻辑上是一样的,不同的是,一是res在全局变量(是这个名字??),更重要的是它设定了一个res的初始值,就避免了使用INT_MIN。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
int res;
public:
int depth(TreeNode *root){
if(root==NULL) return 0;
int a=depth(root->left), b=depth(root->right);
res=max(res,a+b+root->val);//if *root is the top node in the path
return max(0,max(a, b)+root->val);//if *root is in the path, if this branch a burden or a plus
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
res=root->val;
depth(root);
return res;
}
};

https://discuss.leetcode.com/topic/5508/simple-o-n-algorithm-with-one-traversal-through-the-tree

Simple O(n) algorithm with one traversal through the tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
int maxToRoot(TreeNode *root, int &re) {
if (!root) return 0;
int l = maxToRoot(root->left, re);
int r = maxToRoot(root->right, re);
if (l < 0) l = 0;
if (r < 0) r = 0;
if (l + r + root->val > re) re = l + r + root->val;
return root->val += max(l, r);
}
public:
int maxPathSum(TreeNode *root) {
int max = -2147483648;
maxToRoot(root, max);
return max;
}
};

update the val of each node of the tree bottom-up, the new val of TreeNode *x stands for the max sum started from any node in subtree x and ended in x, mataining the re for result in traversal at the same time.

https://discuss.leetcode.com/topic/5508/simple-o-n-algorithm-with-one-traversal-through-the-tree/5

Good solution! Essentially same as mine, but I don’t see why you update the val of each node, since each node is visited only once. In my version, I just return the maximum path ending at the root of the current tree while potentially updating the value of the global maximum with the path that links left and right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maxPathSum(TreeNode *root) {
int max = numeric_limits<int>::min();
maxPathAndGlobalUpdate(root, &max);
return max;
}
private:
int maxPathAndGlobalUpdate(TreeNode *root, int* _global_max) {
if (root == nullptr) return 0;
int& global_max = *_global_max;
int l = max(0, maxPathAndGlobalUpdate(root->left, &global_max));
int r = max(0, maxPathAndGlobalUpdate(root->right, &global_max));
global_max = max(global_max, l + r + root->val);
return root->val + max(l, r);
}
};

42ms, 15.55%, October 14, 2016

A very concise recursive solution

https://discuss.leetcode.com/topic/7325/a-very-concise-recursive-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxPath = INT_MIN;
dfsMaxPath(root, maxPath);
return maxPath;
}

int dfsMaxPath(TreeNode *root, int &maxPath){
if(!root) return 0;
int l = max(0, dfsMaxPath(root->left, maxPath));
int r = max(0, dfsMaxPath(root->right, maxPath));
maxPath = max(maxPath, l+r+root->val);
return root->val + max(l, r);
}
};

https://discuss.leetcode.com/topic/2644/accepted-o-n-solution

Accepted O(n) solution

The idea is based on the solution of max sum of a sequence array, Here is the explaination of the code:

  • Have a recursive method which traverse the binary tree, it also return the max possible sum of left branch and right branch saperately. for example, For node A, when it’s left and right node recusive call returned, we will know the max possible sum of left branch, right branch.

  • Have a CheckMax function which will compare the sequence sum and record the max history. For node A, check whether left branch + this node + right branch is the maximum, check whether left branch + this node is max, check whether right branch + this node is max.

  • When recursive method return, we should only return the max sum of one path - either the left branch + this node, or the right branch + this node. So that this is still a single path and can be used to link by node A’s parent node.

It’s accepted by OL. Let me know if you have any question

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int maxPathSum(TreeNode *root) {
if(!root) return 0;
maxSum = root->val;
recNodes(root);
return maxSum;
}

protected:
int recNodes(TreeNode* node)
{
int numl=0,numr=0;
if (node->left)
numl = recNodes(node->left);
if (node->right)
numr = recNodes(node->right);

//choose the max path, either left or right
int value = node->val;
int sumWhole = checkMax(value,numl+numr);
int sumLeft = numl>0?checkMax(value,numl):value;
int sumRight = numr>0?checkMax(value,numr):value;

return max(sumLeft,sumRight);
}

int checkMax(int value, int sum)
{
if(sum>0)
sum+=value;
else
sum=value;
if(sum>maxSum)
maxSum = sum;
return sum;
}

int maxSum;
};

https://discuss.leetcode.com/topic/35300/recommend-for-beginners-clean-c-implementation-with-detailed-explanation

[recommend for beginners]clean C++ implementation with detailed explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
int sum;
public:
int maxPathSum(TreeNode* root) {
sum=INT_MIN;
help(root);
return sum;
}

/*** return the max-value-ended-at-root-node ***/
int help(TreeNode* root){
if(!root) return 0;
int left = max(0, help(root->left));
int right = max(0, help(root->right));
/*** key parts : embedding the max-value-find in the recursion process ***/
sum = max(sum, left+right+root->val);
/*** get the max-value-ended-at-root ***/
return max(left, right)+root->val;
}
};

https://discuss.leetcode.com/topic/11112/clean-c-solution

Clean c++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
int res;
public:
int depth(TreeNode *root){
if(root==NULL) return 0;
int a=depth(root->left), b=depth(root->right);
res=max(res,a+b+root->val);//if *root is the top node in the path
return max(0,max(a, b)+root->val);//if *root is in the path, if this branch a burden or a plus
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
res=root->val;
depth(root);
return res;
}
};

2ms, 42.51%, October 14, 2016

https://discuss.leetcode.com/topic/4407/accepted-short-solution-in-java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
int maxValue;

public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}

private int maxPathDown(TreeNode node){
if(node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left+right+node.val);
return Math.max(left, right) + node.val;
}
}
谢谢你,可爱的朋友。