Maximum Path Sum
BINARY TREE
DYNAMIC PROGRAMMING
DEPTH-FIRST SEARCH

Problem

Given the root of a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.

The path must contain at least one node and does not need to go through the root.

Examples

// Tree structure: // 1 // / \ // 2 3 maxPathSum([1,2,3]) // returns 6 // The max path is 2 -> 1 -> 3 // Tree structure: // -8 // / \ // 2 4 // / \ // 3 1 maxPathSum([-8,2,4,null,null,3,1]) // returns 8 // The max path is 3 -> 4 -> 1
Loading...
1
2
3