FastPrepMaximum Sum Path Between Two Leaf Nodes
Problem · Tree

Maximum Sum Path Between Two Leaf Nodes

Learn this problem
● HardGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

Given the root of a binary tree whose nodes contain integer values, return the maximum sum of the node values along a simple path whose two endpoints are distinct leaves.

A leaf is a node with no children. The input is guaranteed to contain at least two leaves, so a valid leaf-to-leaf path always exists.

The path may pass through any common ancestor, does not need to pass through the root, and may contain negative values. Its sum includes both leaf endpoints and every intermediate node.

Function

maxLeafToLeafPathSum(root: TreeNode) → long

Examples

Example 1

root = [1,2,3]return = 6

The only leaf-to-leaf path is 2 - 1 - 3, whose node values sum to 6.

Example 2

root = [-10,9,20,null,null,15,7]return = 42

The maximum path is 15 - 20 - 7, whose node values sum to 42. It does not pass through the root.

Example 3

root = [-1,-2,-3]return = -6

All values are negative, but the path must still connect the two leaves. The path -2 - -1 - -3 sums to -6.

Constraints

  • The tree contains between 3 and 100000 nodes, inclusive.
  • -10^9 <= node.val <= 10^9
  • The tree contains at least two distinct leaves.
  • Every leaf-to-leaf path sum fits in a signed 64-bit integer.

More Google problems

drafts saved locally
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 * }
 */
public long maxLeafToLeafPathSum(TreeNode root) {
  // Write your code here.
}
root[1,2,3]
expected6
checking account