1130. Minimum Cost Tree From Leaf Values ======================================== 题目信息 -------- :题号: 1130 :难度: Medium :主题: 数组、二叉树构造、最小代价 :原题: `LeetCode 1130 `_ :重点: 叶节点中序顺序必须等于 ``arr``;每个非叶节点值为左右子树最大叶值的乘积,目标是最小化非叶节点值总和 题目重述 -------- 给定正整数数组 ``arr``。考虑所有满足以下条件的二叉树:每个节点要么没有孩子,要么恰有两个孩子;叶节点按中序遍历得到的值序列恰好等于 ``arr``;每个非叶节点的值等于其左子树最大叶值与右子树最大叶值的乘积。 请返回所有合法树中非叶节点值之和的最小值。题目保证答案适合 32 位有符号整数。 ``2 <= arr.length <= 40``,``1 <= arr[i] <= 15``。 自建示例 -------- 三片叶子的两种划分代价相同: .. code-block:: text 输入:arr = [3,5,2] 输出:25 解释:先组合 3 与 5 的代价为 15,再与 2 组合的代价为 10,总计 25;先组合 5 与 2 也得到 10 + 15 = 25。 只有两片叶子: .. code-block:: text 输入:arr = [7,4] 输出:28 解释:唯一合法树只有一个非叶根节点,其值为 7 * 4 = 28。