/124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Hard

Dynamic Programming42.1% acceptance

Given the root node of a binary tree, compute the maximum sum obtainable from any non-empty path. A path is defined as any sequence of nodes where each pair of adjacent nodes is connected by an edge, and each node appears at most once in the sequence. The path does not need to pass through the root.

Example 1

Input: TreeNode(5, TreeNode(4, TreeNode(11)), TreeNode(8, TreeNode(13), TreeNode(4)))

Output: 27

Explanation: The maximum path is 11 -> 4 -> 5 -> 8 -> 4 with sum 27.

Example 2

Input: TreeNode(-3, TreeNode(-2), TreeNode(-1))

Output: -1

Explanation: The maximum path is the single node with value -1.

Constraints

1 <= number of nodes <= 30000
-1000 <= node value <= 1000
Each node appears at most once in any path
Path can start and end at any node

Python (current runtime)

Case 1

Input: TreeNode(2, TreeNode(-1), TreeNode(3))

Expected: 4

Case 2

Input: TreeNode(10, TreeNode(2, TreeNode(20), TreeNode(1)), TreeNode(-25, None, TreeNode(3)))

Expected: 32

Case 3

Input: TreeNode(1, TreeNode(-2, TreeNode(4), TreeNode(5)), TreeNode(3))

Expected: 8