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