Given an array arr of positive integers, consider all binary trees such that:
arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)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.
Example 1:
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32.
24 24
/ \ / 12 4 6 8
/ \ /6 2 2 4
Constraints:
2 <= arr.length <= 401 <= arr[i] <= 152^31).这道题给了一个数组，说是里面都是一棵树的叶结点，说是其组成的树是一棵满二叉树，且这些叶结点值是通过中序遍历得到的，树中的非叶结点值是是其左右子树中最大的两个叶结点值的乘积，满足这些条件的二叉树可能不止一个，现在让找出非叶结点值之和最小的那棵树，并返回这个最小值。这道题的要求挺多的，好在给了一个带图的例子，可以帮助我们理解，通过观察例子，可以发现叶结点值 6，2，4 的顺序是不能变的，但是其组合方式可能很多，若有很多个叶结点，那么其组合方式就非常的多了。题目中给的提示是用动态规划 Dynamic Programming 来做，用一个二维的 dp 数组，其中 dp[i][j] 表示在区间 [i, j] 内的子数组组成的二叉树得到非叶结点值之和的最小值，接下来想状态转移方程怎么写。首先，若只有一个叶结点的话，是没法形成非叶结点的，所以 dp[i][i] 是0，最少得有两个叶结点，才有非0的值，即 dp[i][i+1] = arr[i] * arr[i+1]，而一旦区间再大一些，就要遍历其中所有的小区间的情况，用其中的最小值来更新大区间的 dp 值。这种按区间长度顺序来更新的方法在之前的题目中也出现过，比如 Burst Balloons 和 Remove Boxes。这里的区间长度从1到n，长度为1，表示至少有两个叶结点，i从0遍历到 n-len，j可以直接确定出来为 i+len，然后用k来将区间 [i, j] 分为两个部分，由于分开的小区间在之前都已经更新过了，所以其 dp 值可以直接得到，然后再加上这两个区间中各自的最大结点值的乘积。为了不每次都遍历小区间来获得最大值，可以提前计算好任意区间的最大值，保存在 maxVec 中，这样就可以快速获取了，最后返回的结果保存在 dp[0][n-1] 中，参见代码如下：
解法一：
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n));
vector<vector<int>> maxVec(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
int curMax = 0;
for (int j = i; j < n; ++j) {
curMax = max(curMax, arr[j]);
maxVec[i][j] = curMax;
}
}
for (int len = 1; len < n; ++len) {
for (int i = 0; i + len < n; ++i) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxVec[i][k] * maxVec[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
};
下面的这种解法是参见了大神 lee215 的帖子，是一种利用单调栈来解的方法，将时间复杂度优化到了线性，惊为天人。思路是这样的，当两个叶结点生成一个父结点值，较小的那个数字使用过一次之后就不再被使用了，因为之后形成的结点是要子树中最大的那个结点值。所以问题实际上可以转化为在一个数组中，每次选择两个相邻的数字a和b，移除较小的那个数字，代价是 a*b，问当移除到数组只剩下一个数字的最小的代价。Exactly same problem，所以b是有可能复用的，要尽可能的 minimize，数字a可以是一个局部最小值，那么b就是a两边的那个较小的数字，这里使用一个单调栈来做是比较方便的。关于单调栈，博主之前也有写过一篇总结 LeetCode Monotonous Stack Summary 单调栈小结，在 LeetCode 中的应用也非常多，是一种必须要掌握的方法。这里维护一个最小栈，当前栈顶的元素是最小的，一旦遍历到一个较大的数字，此时当前栈顶的元素其实是一个局部最小值，它就需要跟旁边的一个较小的值组成一个左右叶结点，这样形成的父结点才是最小的，然后将较小的那个数字移除，符合上面的分析。然后继续比较新的栈顶元素，若还是小，则继续相同的操作，否则退出循环，将当前的数字压入栈中。最后若栈中还有数字剩余，则一定是从大到小的，只需将其按顺序两两相乘即可，参见代码如下：
解法二：
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
int res = 0, n = arr.size();
vector<int> st{INT_MAX};
for (int num : arr) {
while (!st.empty() && st.back() <= num) {
int mid = st.back();
st.pop_back();
res += mid * min(st.back(), num);
}
st.push_back(num);
}
for (int i = 2; i < st.size(); ++i) {
res += st[i] * st[i - 1];
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1130
类似题目：
Largest Rectangle in Histogram
参考资料：
https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] 1130. Minimum Cost Tree From Leaf Values 叶值的最小代价生成树
原文：https://www.cnblogs.com/grandyang/p/14826993.html