# 8 lines Python and a shortest 5 lines python for fun

• Regular one:

``````class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.sum = root.val
def dfs(root):
if not root: return 0
l = dfs(root.left)
r = dfs(root.right)
self.sum = max(self.sum, root.val + max(l, r), root.val, root.val + l + r)
return max(root.val, root.val + max(l, r))
return max(dfs(root), self.sum)
``````

Shortest one:

``````class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root):
if not root: return (0, float("-inf"))
(l, lm), (r, rm) = map(dfs, [root.left, root.right])
return (max(root.val, root.val + max(l, r)), max(lm, rm, root.val + max(l, r), root.val, root.val + l + r))
return dfs(root)[1]
``````

• zhen-five line

``````public class Solution {
public int maxPathSum(TreeNode root) {
result = Integer.MIN_VALUE;

search(root);

return result;
}

private int search(TreeNode node) {
if (node == null) return 0;

int leftResult = search(node.left);
int rightResult = search(node.right);

result = Math.max(Math.max(Math.max(Math.max(leftResult, rightResult) + node.val, node.val), leftResult + rightResult + node.val), result);

return Math.max(Math.max(leftResult, rightResult), 0) + node.val;
}

private int result;
}
``````

• @adam47 This is obviously 13 lines. Did you seriously count it?

• This post is deleted!

• @jedihy What are you talking about?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.