1130. Minimum Cost Tree From Leaf Values Medium

1/**
2 * [1130] Minimum Cost Tree From Leaf Values
3 *
4 * Given an array arr of positive integers, consider all binary trees such that:
5 * 
6 * 	Each node has either 0 or 2 children;
7 * 	The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
8 * 	The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
9 * 
10 * 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.
11 * A node is a leaf if and only if it has zero children.
12 *  
13 * Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/tree1.jpg" style="width: 500px; height: 169px;" />
15 * Input: arr = [6,2,4]
16 * Output: 32
17 * Explanation: There are two possible trees shown.
18 * The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
19 * 
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/tree2.jpg" style="width: 224px; height: 145px;" />
22 * Input: arr = [4,11]
23 * Output: 44
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	2 <= arr.length <= 40
29 * 	1 <= arr[i] <= 15
30 * 	It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 2^31).
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
36// discuss: https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn mct_from_leaf_values(arr: Vec<i32>) -> i32 {
42        0
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_1130() {
54    }
55}
56