FastPrepBinary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

ByteDance logoByteDance● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Return the largest sum of node values on any nonempty simple path in a binary tree. A path uses parent-child edges, visits each node at most once, and may begin and end anywhere; it need not include the root.

For this exercise, use the conventional maximum-path-sum interpretation of the named tree exercise. The arrays values, left and right describe node indices: root is 0, child index -1 means absent, and all other indices identify children. Inputs describe one valid connected binary tree. Return the sum as a signed 64-bit integer.

Function

maximumPathSum(values: int[], left: int[], right: int[]) → long

Examples

Example 1

values = [-10,9,20,15,7]left = [1,-1,3,-1,-1]right = [2,-1,4,-1,-1]return = 42

The best path is node 3 to node 2 to node 4, totaling 15+20+7.

Example 2

values = [-3]left = [-1]right = [-1]return = -3

A nonempty path is required even when every value is negative.

Example 3

values = [1,2,3]left = [1,-1,-1]right = [2,-1,-1]return = 6

The path through both children and the root has sum 6.

Constraints

  • The three arrays have the same length 1 <= n <= 200.
  • -10^6 <= values[i] <= 10^6.
  • Child indices are -1 or valid node indices. Node 0 is the root; every other node has exactly one parent.
  • The input is connected and acyclic. The path contains at least one node.

More ByteDance problems

See ByteDance hiring insights
public long maximumPathSum(int[] values, int[] left, int[] right) {
    // Write your code here.
}
values[-10,9,20,15,7]
left[1,-1,3,-1,-1]
right[2,-1,4,-1,-1]
expected42
Checking account…