LeetCode 补充题 132. 加分二叉树
题目描述
牛客原题： ✅ 补充题 132. 加分二叉树
给你一个正整数数组
scores，表示编号为1到n的节点分数，节点i的分数为scores[i - 1]。请用全部节点构造一棵二叉树，使中序遍历的节点编号依次为1, 2, …, n。一棵子树的得分按以下规则计算：
- 空子树的得分为
1。- 叶子节点的得分就是它自身的分数。
- 非叶子子树的得分为
左子树得分 × 右子树得分 + 根节点分数。请返回能够获得的最大得分，以及任意一棵最优二叉树的前序编号序列。结果对象分别保存任意精度整数得分和前序数组。
示例 1：
输入：
scores = [5,7,1,2,10]
输出：最大分数 = 145, 前序编号 = [3,1,2,4,5]
解释： 选 3 为根，左子树得分为 12，右子树得分为 12，所以总分为 12×12+1=145；中序编号仍为 1、2、3、4、5。
提示：
- 节点编号为
1…n，必须构成中序遍历顺序。 - 节点分数为正整数。
- 空子树得分为
1，叶子得分直接等于自身分数。 - 返回大整数得分和一棵最优树的前序编号。
题意分析
中序编号固定后，根的编号就确定了左右子树各自使用的连续区间，不能随意分配节点。因此枚举根后，左右两部分都变成同类型的更小区间问题，可以用区间动态规划。
解法：区间枚举根并记录最优结构
核心思路
[!blue]
dp[l][r]表示编号对应区间内能够获得的最大得分，roots[l][r]记录取得该分数的根下标。选择k为根时，左区间为[l,k-1]，右区间为[k+1,r]；空区间按得分 1 处理。节点分数都是正数，乘积随左右得分增大而增大，所以固定根后，两边可以各自取最大值，再计算
left * right + scores[k]。枚举所有根并取最大，就覆盖了当前区间全部合法树形。单节点必须单独初始化为自身分数，不能错误套成1 * 1 + score。按区间长度递增计算，使依赖的子区间先完成。最后从完整区间出发，依次输出根编号、左区间前序、右区间前序。乘加使用大整数，Go 用新的
big.Int保存候选，避免改写已存的子问题结果。
解题步骤
- 单节点区间直接取节点分数，空子树按乘法单位元 1 处理。
- 按区间长度递增枚举根，以左分数乘右分数再加根分数更新最优值。
- 保存取得最优值的根下标，同分时保留先枚举的较小根。
- 根据根表按根、左、右恢复前序编号，并返回大整数分数。
代码实现
class Solution {
static class Result {
BigInteger score;
int[] preorder;
Result(BigInteger score, int[] preorder) {
this.score = score;
this.preorder = preorder;
}
}
private void preorder(int l, int r, int[][] roots, List<Integer> out) {
if (l > r) {
return;
}
int k = roots[l][r];
out.add(k + 1);
preorder(l, k - 1, roots, out);
preorder(k + 1, r, roots, out);
}
public Result bestTree(int[] scores) {
int n = scores.length;
BigInteger[][] dp = new BigInteger[n][n];
int[][] roots = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = BigInteger.valueOf(scores[i]);
roots[i][i] = i;
}
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len <= n; l++) {
int r = l + len - 1;
for (int k = l; k <= r; k++) {
BigInteger left = k == l ? BigInteger.ONE : dp[l][k - 1];
BigInteger right = k == r ? BigInteger.ONE : dp[k + 1][r];
BigInteger value = left.multiply(right).add(BigInteger.valueOf(scores[k]));
if (dp[l][r] == null || value.compareTo(dp[l][r]) > 0) {
dp[l][r] = value;
roots[l][r] = k;
}
}
}
}
List<Integer> list = new ArrayList<>();
preorder(0, n - 1, roots, list);
int[] order = list.stream().mapToInt(Integer::intValue).toArray();
return new Result(dp[0][n - 1], order);
}
}
import "math/big"
type TreeResult struct {
Score *big.Int
Preorder []int
}
func bestTree(scores []int) TreeResult {
n := len(scores)
dp := make([][]*big.Int, n)
roots := make([][]int, n)
for i := range dp {
dp[i] = make([]*big.Int, n)
roots[i] = make([]int, n)
dp[i][i] = big.NewInt(int64(scores[i]))
roots[i][i] = i
}
for length := 2; length <= n; length++ {
for l := 0; l+length <= n; l++ {
r := l + length - 1
for k := l; k <= r; k++ {
left, right := big.NewInt(1), big.NewInt(1)
if k > l {
left = dp[l][k-1]
}
if k < r {
right = dp[k+1][r]
}
value := new(big.Int).Mul(left, right)
value.Add(value, big.NewInt(int64(scores[k])))
if dp[l][r] == nil || value.Cmp(dp[l][r]) > 0 {
dp[l][r] = value
roots[l][r] = k
}
}
}
}
order := []int{}
var visit func(int, int)
visit = func(l, r int) {
if l > r {
return
}
k := roots[l][r]
order = append(order, k+1)
visit(l, k-1)
visit(k+1, r)
}
visit(0, n-1)
return TreeResult{dp[0][n-1], order}
}
复杂度分析
- 时间复杂度：$O(n^3)$ 次大整数乘加与比较，另需 $O(n)$ 次节点访问恢复前序；实际位运算成本还取决于得分长度。
- 空间复杂度：$O(n^2)$ 个大整数及根下标，另有最多 $O(n)$ 的重建调用栈和输出。
关键点总结
[!green]
固定中序把结构选择化成区间根选择；正分数保证左右子树可以各自取最优，再通过根表恢复具体结构。
易错点总结
[!yellow]
叶子不是1×1+d；空子树取1；重建时输出节点编号，不是分数；不要在比较之前取模或转int。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 96. 不同的二叉搜索树 | 中等 | 同样按根拆成左右中序区间，原题统计树的数量，本题优化分数。 |
| 95. 不同的二叉搜索树 II | 中等 | 都依赖中序区间决定左右子树，本题只记录最优根并恢复一棵树，不枚举全部结构。 |