• 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.

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

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

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

code 1：

code 2：

code 3：

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

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

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

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.

42ms, 15.55%, October 14, 2016

A very concise recursive solution

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

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

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

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

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

Clean c++ solution

2ms, 42.51%, October 14, 2016

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