So the way I thought of this problem is we are finding the maximum path for a node's left and right subtrees, and then combining them with the node to form the maximum path for the entire tree. However there are some conditions we have to be aware of:
A single node can be the maximum path for the entire tree
The root may not be part of the final maximum path
So what I did was run DFS on the tree, and then for every node I check whether I should include the left or child's max path sum, or just skip them.
This was the logic I followed:
If the left or right pathsum added to the node's value results in a larger sum, then include it. If neither does, discard them.
If the left or right path sum combined with the node results in a larger pathsum than the pathsum of the entire tree, return that path sum instead. (We store subtree's combined pathsum in a variable and update it everytime we encounter a larger one).
def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ if not root: return self.subMax = float("-inf") return max(self._helper(root), root.val, self.subMax) def _helper(self, root): if not root: return float("-inf") if not root.left and not root.right: return root.val leftSum = self._helper(root.left) rightSum = self._helper(root.right) curMax = max(root.val, root.val+leftSum, root.val+rightSum) if leftSum > curMax: self.subMax = max(self.subMax, leftSum) if rightSum > curMax: self.subMax = max(self.subMax, rightSum) if rightSum + leftSum + root.val > curMax: self.subMax = max(self.subMax, rightSum + leftSum + root.val) return curMax
I got beats 99.38% of Python solution. Looking at other solutions, I think its because I'm doing conditional checks instead of assigning left and right subtree's sums to 0 if they are less than then node's value.