AlgoLounge

Binary Tree Maximum Path Sum

hard

LeetCode 124. Binary Tree Maximum Path Sum

Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear in the sequence once. The path does not necessarily need to include the root.

The path sum of a path is the sum of the node's values in the path.

Examples

Example 1

Input:  root = [1,2,3]

1 / \ 2 3Output: 6 Path 2 → 1 → 3 has maximum sum 2 + 1 + 3 = 6

Example 2

Input:  root = [-10,9,20,null,null,15,7]
Output: 42

Path 15 → 20 → 7 has maximum sum 15 + 20 + 7 = 42

Constraints

  • 1 <= The number of nodes in the tree <= 1000
  • -1000 <= Node.val <= 1000

How the tests work: trees are written as level-order arrays — [1,null,2] is a root 1 with a right child 2. Your function receives real TreeNode objects.

TypeScript
Loading editor…
List of test cases (10)
Case 1
root = [1,2,3]
Case 2
root = [-10,9,20,null,null,15,7]
Case 3
root = [-3]
Case 4
root = [2,-1]
Case 5
root = [1]
Case 6
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
Case 7
root = [1,2,null,3,null,4,null,5]
Case 8
root = [-1,-2,-3]
Case 9
root = [6,2,3,null,null,null,1]
Case 10
root = [9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6]