資訊專欄INFORMATION COLUMN
摘要：動態規劃練習題總題目描述設一個個節點的二叉樹的中序遍歷為，其中數字為節點編號。若某個子樹為空，規定其加分為，葉子的加分就是葉節點本身的分數。試求一棵符合中序遍歷為且加分最高的二叉樹。
動態規劃練習題-總
題目描述
設一個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次方)
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/110053.html
摘要：很多前端同學在看到數據結構和算法后會有一定的抵觸心理，或者嘗試去練習，但是被難倒，從而放棄。本文選擇的數據結構和算法的類別均是出現頻率最高，以及應用最廣的類別。面試這是非常現實的一點，也是很多前端學習數據結構和算法的原因。 一、導讀 據我了解，前端程序員有相當一部分對數據結構和算法的基礎概念都不是很清晰，這直接導致很多人在看到有關這部分的內容就會望而卻步。 實際上，當你了解了數據結構和...
摘要：上一篇數據結構與算法集合字典一遞歸學習樹離不開遞歸。先序遍歷的一種應用是打印一個結構化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節點的后代節點，再訪問節點本身。 上一篇：JS數據結構與算法_集合&字典 一、遞歸 學習樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數調用自身。 通俗的解釋：年級...
閱讀 2922·2021-11-24 09:39
閱讀 3599·2021-11-22 13:54
閱讀 3409·2021-11-16 11:45
閱讀 2432·2021-09-09 09:33
閱讀 3194·2019-08-30 15:55
閱讀 1290·2019-08-29 15:40
閱讀 920·2019-08-29 15:19
閱讀 3396·2019-08-29 15:14
