class Solution: def maxPathSum(self, root: TreeNode) -> int: res = [root.val] # return max path sum without split def dfs(root): if not root: return 0 leftMax = dfs(root.left) rightMax = dfs(root.right) leftMax = max(leftMax, 0) rightMax = max(rightMax, 0) # compute max path sum WITH split res[0] = max(res[0], root.val + leftMax + rightMax) return root.val + max(leftMax, rightMax) dfs(root) return res[0]
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter