设一个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的前序遍历

数据范围： $设一个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的前序遍历数据范围：，每个节点的值满足$ ，每个节点的值满足 $设一个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链游项目方科学家脚本开发培训