# 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

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

``````