#1130
Minimum Cost Tree From Leaf Values
pupil · 595 · lc medium +29 · verified · 67.8% accepted · 4,431 likes · top 74%
Description
Given an array arr of positive integers, consider all binary trees where:
- Every internal node has exactly two children.
- The values of arr appear as leaf values in an in-order traversal.
- Each internal node's value equals the product of the largest leaf values in its left and right subtrees.
Return the minimum possible sum of all internal node values. Answers fit in a 32-bit integer.
A node is a leaf if and only if it has zero children.
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation: There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
Example 2:
Input: arr = [4,11]
Output: 44
Code
1
2
3