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 <= 40
1 <= arr[i] <= 15
2^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