Maximum Path Sum Between Marked Nodes
Problem statement
A binary tree has n nodes numbered from 0 to n - 1, and node 0 is the root. Node i has the value values[i], the left child left[i] and the right child right[i]. A child of -1 means there is no child on that side.
Some nodes are marked, and marked lists their ids. A marked node can be a leaf or any other node, including the root.
Between two different nodes a and b there is exactly one path: go up from a to the lowest node that has both a and b in its subtree, then go down to b. If one of the two nodes is above the other, the path is just the straight line between them. The sum of a path is the total of the values of all nodes on it, including both ends.
Find the path with the largest sum among all paths whose two ends are two different marked nodes. The nodes in the middle of the path can be marked or not. Return the path as a list of node ids, from one end to the other.
To make the answer unique:
- Write the ends of a path as
(a, b)witha < b. Return the path starting ataand ending atb. - If several paths have the largest sum, return the one with the smallest
a. If there is still a tie, return the one with the smallestb.
Function
bestMarkedPath(values: int[], left: int[], right: int[], marked: int[]) → int[]Examples
Example 1
values = [5,2,0,25,14,15]left = [1,3,4,-1,-1,-1]right = [2,-1,5,-1,-1,-1]marked = [3,4,5]return = [3,1,0,2,5]Only the leaves 3, 4 and 5 are marked, so there are three possible paths:
3 → 1 → 0 → 2 → 4has sum25 + 2 + 5 + 0 + 14 = 46.3 → 1 → 0 → 2 → 5has sum25 + 2 + 5 + 0 + 15 = 47.4 → 2 → 5has sum14 + 0 + 15 = 29.
The largest sum is 47. Its smaller end is 3, so the path is listed from 3 to 5.
Example 2
values = [-2,8,3,-4,-1,-6]left = [1,3,-1,-1,-1,-1]right = [2,4,5,-1,-1,-1]marked = [5,1,4]return = [1,4]Node 1 is marked even though it is not a leaf, so it can be an end. Node 3 is not marked, so no path can end there.
1 → 4has sum8 + (-1) = 7.1 → 0 → 2 → 5has sum8 + (-2) + 3 + (-6) = 3.4 → 1 → 0 → 2 → 5passes through the marked node1, which is allowed. Its sum is(-1) + 8 + (-2) + 3 + (-6) = 2.
The largest sum is 7. Node 1 alone would have sum 8, but it does not count, because the two ends must be different nodes.
Example 3
values = [0,5,5,0]left = [1,-1,-1,-1]right = [2,-1,3,-1]marked = [3,2,1]return = [1,0,2]1 → 0 → 2has sum5 + 0 + 5 = 10.1 → 0 → 2 → 3has sum5 + 0 + 5 + 0 = 10.2 → 3has sum5 + 0 = 5.
Two paths tie with sum 10. Their ends are (1, 2) and (1, 3). The smaller ends are both 1, so compare the other ends: 2 is smaller than 3. The answer is the path between 1 and 2, listed from 1.
Constraints
n == values.length == left.length == right.length2 <= n <= 500-1000 <= values[i] <= 1000- Each
left[i]andright[i]is-1or a node id from1ton - 1. - Every node from
1ton - 1is the child of exactly one node, and every node can be reached from node0. So the arrays form one binary tree with root0. 2 <= marked.length <= n- The ids in
markedare distinct, and each one is from0ton - 1.