1130. Minimum Cost Tree From Leaf Values
Medium
30 Points
Array
Dynamic Programming
Stack
Greedy
Monotonic Stack
Given an array arr of positive integers, consider all binary trees such that:
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
Examples
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
Constraints
2 <= arr.length <= 401 <= arr[i] <= 15It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).
1130. Minimum Cost Tree From Leaf Values
Medium
30 Points
Array
Dynamic Programming
Stack
Greedy
Monotonic Stack
Given an array arr of positive integers, consider all binary trees such that:
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
Examples
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
Constraints
2 <= arr.length <= 401 <= arr[i] <= 15It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).