# 124. Binary Tree Maximum Path Sum¶

## Intuition¶

Based on the description of this problem, the path of a tree could be defined by 3 nodes, the sub-root node, the left virtual leaf node and the right virtual leaf. And we could get the sum by traveral 2 path, one from the left virtual leaf to the sub-root, another from the right virtual leaf to the sub-root.

So this problem could be solved using DFS with the code like below. The `_helper` method is for DFS. The return value of this method is the maximum path from the node to any nodes in its subtree.

## Solution¶

```class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.maxpath = root.val
self._helper(root)
return self.maxpath

def _helper(self, node):
if node is None:
return 0
l = self._helper(node.left)
r = self._helper(node.right)
self.maxpath = max(
self.maxpath,
node.val,
node.val + l,
node.val + r,
node.val + r + l
)
return max(l, r, 0) + node.val
```

## Information¶

• Created: 2020-01-12 17:13:18

• Last Motified: 2020-01-12 17:13:18

• Tags: Tree, Depth-first Search