设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出： （1）tree的最高加分 （2）tree的前序遍历 数据范围： ，每个节点的值满足
区块链毕设网qklbishe.com为您提供问题的解答
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出：
（1）tree的最高加分
（2）tree的前序遍历
数据范围： 
，每个节点的值满足 
暴力递归加记忆化，递归函数buildMaxScoreTree构建树，参数为固定的分数列表scores，当前中序遍历输出的scores对应的index，构建一颗多少节点的树nodeNum,以及缓存最大分数树的结果的二维数组dp，最后再对树进行先序遍历
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param scores int整型ArrayList * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> scoreTree (ArrayList<Integer> scores) { ArrayList<Integer> pre = new ArrayList<>(); Node[][] dp = new Node[scores.size() + 1][scores.size() + 1]; Node root = buildMaxScoreTree(scores, 0, scores.size(), dp); ArrayList<ArrayList<Integer>> res = new ArrayList<>(); int s = root.addScore; ArrayList<Integer> scoreList = new ArrayList<>(); scoreList.add(s); res.add(scoreList); visitNode(root, pre); res.add(pre); return res; } private void visitNode(Node node, ArrayList<Integer> pre) { if (node == null) { return; } pre.add(node.nodeIndex); visitNode(node.left, pre); visitNode(node.right, pre); } private static class Node { private int nodeIndex; private int addScore; private int score; private Node left; private Node right; } private Node buildMaxScoreTree(ArrayList<Integer> scores, int index, int nodeNum, Node[][] dp) { if (dp[index][nodeNum] != null) { return dp[index][nodeNum]; } if (nodeNum == 0) { return null; } Node node = new Node(); if (nodeNum == 1) { node.score = scores.get(index); node.addScore = scores.get(index); node.nodeIndex = index + 1; dp[index][nodeNum] = node; return node; } int maxScore = 0; Node maxLeft = null; int nodeIndex = 0; Node maxRight = null; int mscore = 0; for (int i = 0; i < nodeNum; i++) { Node left = buildMaxScoreTree(scores, index, i, dp); int leftScore = left == null ? 1 : left.addScore; int score = scores.get(index + i); int rightNodeNum = nodeNum - i - 1; Node right = buildMaxScoreTree(scores, index + i + 1, rightNodeNum, dp); int rightScore = right == null ? 1 : right.addScore; int theAddScore = leftScore * rightScore + score; if (theAddScore > maxScore) { maxLeft = left; maxRight = right; maxScore = theAddScore; mscore = score; nodeIndex = index + i + 1; } } node.addScore = maxScore; node.left = maxLeft; node.right = maxRight; node.score = mscore; node.nodeIndex = nodeIndex; dp[index][nodeNum] = node; return node; } }
编辑于 今天 17:31:10
以上就是关于问题设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出： （1）tree的最高加分 （2）tree的前序遍历
数据范围： ，每个节点的值满足的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
![定义一个数组的价值是第一个位置的数字乘以 8，加上第二个数字乘以 7，加第三个数字乘以 6。。。例如一个数组 [1,2,3,4,5,6,7,8] 的价值为 现在有一个长度为 8 的数组，仅包含 这些数字各一个，你每次可以交换两个相邻且互质的数字（互质即最大公约数为 1），已知你能够将这个数组最终交换成 [1,2,3,4,5,6,7,8]。我们可以发现符合这一要求的原数组有多种可能，请问在这些所有的可能中，原数组的最大价值是（ ）](data:image/gif;base64,R0lGODlhAQABAAAAACH5BAEKAAEALAAAAAABAAEAAAICTAEAOw==)
