1130. Minimum Cost Tree From Leaf Values

题目信息

题号:

1130

难度:

Medium

主题:

数组、二叉树构造、最小代价

原题:

LeetCode 1130

重点:

叶节点中序顺序必须等于 arr;每个非叶节点值为左右子树最大叶值的乘积,目标是最小化非叶节点值总和

题目重述

给定正整数数组 arr。考虑所有满足以下条件的二叉树:每个节点要么没有孩子,要么恰有两个孩子;叶节点按中序遍历得到的值序列恰好等于 arr;每个非叶节点的值等于其左子树最大叶值与右子树最大叶值的乘积。

请返回所有合法树中非叶节点值之和的最小值。题目保证答案适合 32 位有符号整数。

2 <= arr.length <= 40,1 <= arr[i] <= 15。

自建示例

三片叶子的两种划分代价相同:

输入:arr = [3,5,2]
输出:25
解释:先组合 3 与 5 的代价为 15,再与 2 组合的代价为 10,总计 25;先组合 5 与 2 也得到 10 + 15 = 25。

只有两片叶子:

输入:arr = [7,4]
输出:28
解释:唯一合法树只有一个非叶根节点,其值为 7 * 4 = 28。