动态规划练习题-加分二叉树

Miracle 发布于2019-08-26 14:06 / 3422人阅读

摘要：动态规划练习题总题目描述设一个个节点的二叉树的中序遍历为，其中数字为节点编号。若某个子树为空，规定其加分为，叶子的加分就是叶节点本身的分数。试求一棵符合中序遍历为且加分最高的二叉树。

动态规划练习题-总

题目描述
设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出tree的最高加分和前序遍历
输入
长度为n的序列，序列值为每个节点的分数（分数＜100）如：5,7,1,2,10
输出
最高加分；前序遍历，如：145; 3 1 2 4 5

1 思路
若要使加分最高，则需让父节点尽可能小

2 拆分子问题
构建树的过程中，从当前序列找到值最小的节点作为父节点，节点左侧序列为左子树，右侧序列为右子树

3 计算
T[0,m]={ Node[k], left:T[0,k-1], right:T[k+1,m]}

4 代码
recursive DP

const treeArray = [5,7,1,2,10];
class CalTree {
  constructor(options) {
    this.treeArray = Array.isArray(options) ? options : [];
    this.walkArr = [];
    this.sum = 0;
  }
  getTreeRecursive() {
    const newArr = this.getTreeRec(this.treeArray);
    this.sum = this.getSum(newArr);
    console.log(`前序遍历序列是: ${ this.walkArr.join(",") }`);
    console.log(`最高加分是 ${this.sum}`); // 最高得分
  }
  getTreeRec(arr) {
    const min = Math.min(...arr);
    const item = {
      value: min,
      index: arr.indexOf(min)
    };
    if (arr.length === 1) {
      return {
        item,
        left: null,
        right: null
      };
    }
    const leftArr = arr.slice(0, item.index);
    const rightArr = arr.slice(item.index + 1, arr.length);
    let obj = {};
    obj.item = item;
    obj.left = leftArr.length > 0 ? this.getTreeRec(leftArr):null;
    obj.right = rightArr.length > 0 ? this.getTreeRec(rightArr) : null;
    return obj;
  }
  getSum(obj) {
    this.walkArr.push(obj.item.value);
    if (!obj.left && !obj.right) {
      return obj.item.value;
    }
    const left = obj.left ? this.getSum(obj.left) : 1;
    const right = obj.right ? this.getSum(obj.right) : 1;
    return obj.item.value + left * right;
  }

}
new CalTree(treeArray).getTreeRecursive();

5 时间复杂度
主要过程是把序列一分为二分别建子树，第i次拆分的计算量是2的i次方，故时间复杂度为O(2的logn次方)

GPU云服务器云服务器二叉树 python二叉树平衡二叉树实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/110053.html

动态规划练习题-总

摘要：最近学习了动态规划的四节网课，想上手练习，故写文章留作纪念，文章的主要内容是解题思路，代码用写练习题分为四种，线性动规拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等，区域动规石子合并，加分二叉树，统计单词个数，炮兵布阵等，树形动规贪吃的九头最近学习了动态规划的四节网课，想上手练习，故写文章留作纪念，文章的主要内容是解题思路，代码用JS写练习题分为四种：1，线性动规：拦截导弹，合唱队...

yacheng 2019-08-26 14:01 评论0 收藏0
前端该如何准备数据结构和算法？

摘要：很多前端同学在看到数据结构和算法后会有一定的抵触心理，或者尝试去练习，但是被难倒，从而放弃。本文选择的数据结构和算法的类别均是出现频率最高，以及应用最广的类别。面试这是非常现实的一点，也是很多前端学习数据结构和算法的原因。一、导读据我了解，前端程序员有相当一部分对数据结构和算法的基础概念都不是很清晰，这直接导致很多人在看到有关这部分的内容就会望而却步。实际上，当你了解了数据结构和...

simon_chen 2019-08-26 14:04 评论0 收藏0
JS数据结构与算法_树

摘要：上一篇数据结构与算法集合字典一递归学习树离不开递归。先序遍历的一种应用是打印一个结构化的文档下面的图描绘了先序遍历方法的访问路径后序遍历后序遍历则是先访问节点的后代节点，再访问节点本身。上一篇：JS数据结构与算法_集合&字典一、递归学习树离不开递归。 1.1 介绍递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。递归通常涉及函数调用自身。通俗的解释：年级...

tabalt 2019-08-26 13:35 评论0 收藏0