Minimum Root-to-Leaf Cut Cost
Problem statement
You are given a rooted binary tree whose edges have nonnegative integer costs. Choose a set of edges to cut so that the root is disconnected from every leaf of the original tree. Return the minimum possible sum of the cut-edge costs.
The tree is encoded by four arrays of equal length n. Node 0 is the root. For each node i, leftChild[i] and rightChild[i] are its child indices, or -1 when that child is absent. When a child is present, the matching entry in leftCost or rightCost is the cost of that edge; when it is absent, the matching cost is 0.
A leaf is determined from the original tree: it is a node with no children before any cuts. Cutting an edge may disconnect many original leaves at once. Nodes that become leaves only because of earlier cuts do not add new requirements.
If all four arrays are empty, or if the tree contains only its root, return 0.
Interview follow-up
The primary problem requires nonnegative edge costs. With negative costs, an optimal answer may cut extra edges even after a leaf is already disconnected, so the primary recurrence no longer applies unchanged.
Function
minimumRootLeafCutCost(leftChild: List<Integer>, rightChild: List<Integer>, leftCost: List<Integer>, rightCost: List<Integer>) → longExamples
Example 1
leftChild = [1,3,5,-1,-1,-1,-1]rightChild = [2,4,6,-1,-1,-1,-1]leftCost = [4,1,6,0,0,0,0]rightCost = [7,5,2,0,0,0,0]return = 11Below node 1, cutting both leaf edges costs 1 + 5 = 6, so cutting the root-to-1 edge for 4 is cheaper. Below node 2, the leaf edges cost 6 + 2 = 8, so cutting the root-to-2 edge for 7 is cheaper. The minimum total is 4 + 7 = 11.
Example 2
leftChild = [1,2,3,-1]rightChild = [-1,-1,-1,-1]leftCost = [8,3,5,0]rightCost = [0,0,0,0]return = 3There is one root-to-leaf path. Cutting its middle edge, from node 1 to node 2, costs 3, which is cheaper than cutting either other edge.
Example 3
leftChild = [-1]rightChild = [-1]leftCost = [0]rightCost = [0]return = 0The root-only case has no edge that can be cut, and the required result is 0.
Constraints
0 <= n <= 2147483647- All four arrays have length
n. - When
n > 0, the child indices form one valid binary tree rooted at node0: every node other than0appears exactly once as a child, and every node is reachable from the root. - Each child index is
-1or lies between0andn - 1. - An absent child has matching edge cost
0. A present edge has cost between0and2147483647, inclusive. - The sum of all edge costs is at most
2147483647.