給定一棵總共有n個節點的二叉樹，每個節點都有一定數量的 cookie，總和為n個cookies。
任務是將其轉換為具有相同 cookie（每個節點 1 個 cookie）且傳輸總成本最低的節點，前提是傳輸成本等于在節點本身之間傳輸的 cookie 數量。
Cookie 只能在 a) 父級到子級 b) 子級到父級之間傳輸
例子，
在下面的例子中，第一個 1 cookie 可以從左孩子轉移到父母，成本 = 1，然后轉移到右孩子，使其在所有節點上相等，額外成本為 1。所以最小總成本為 2。
1 2 1
2 0 =====> 1 0 =====> 1 1
(given tree) (transformed tree)
Minimum cost of transfer = 2
我們可以有一個最佳（時間）演算法來解決這個問題嗎？
uj5u.com熱心網友回復：
您可以使用后序（深度優先）遍歷從每個子樹中收集兩個資訊。定義：
的偏差：它是之間的差預期餅干的數目（即節點的該子樹的數目），以及在該子樹的Cookie的實際數目。如果為負，則表示 cookie 不足，并且可以肯定，此數量的 cookie 必須通過此子樹的父級來自其他地方。如果為正，則表示 cookie 剩余，并且該剩余將需要從該子樹移出到父節點。因此，無論是負數還是正數，它的絕對值都表示此子樹的根與其父級之間的 cookie 流。
該子樹內的轉移成本。這表示移動沿著邊緣餅干的成本之內的子樹，既填補缺失的Cookie，并從有不止一個節點移開餅干。它還包括將所有剩余 cookie 向上冒泡到子樹根節點的成本，不包括將它們從那里移到父節點的成本。它還包括將來自父節點的 cookie 進一步向下分發到子樹的成本，但不包括將這些 cookie 從父節點獲取到根節點的成本。
這里存在遞推關系。當您擁有給定節點的左右子樹的這對資訊時，您可以為組合樹（其中給定節點是根）推匯出該對資訊：
在偏離當前樹（植根于一個給定的節點）是它的兩個子樹的偏差之和在當前節點減1的cookie的數量“減1”體現了目標，必須在1塊餅干當前節點。
該成本對于當前的樹（植根于一個給定的節點）是成本之和發現它的兩個子樹和的絕對值偏差發現此節點（參見前一點）。
這是一個可運行的 JavaScript 代碼段的實作。它針對以下樹運行：
2
/ \
0 1
/ \
0 2
答案是 3。
class Node {
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
transferDiffAndCost() {
let diffLeft = 0, diffRight = 0, costLeft = 0, costRight = 0;
if (this.left) {
[diffLeft, costLeft] = this.left.transferDiffAndCost();
}
if (this.right) {
[diffRight, costRight] = this.right.transferDiffAndCost();
}
let diff = diffLeft diffRight this.value - 1;
let cost = costLeft costRight Math.abs(diff);
return [diff, cost];
}
transferCost() {
let [diff, cost] = this.transferDiffAndCost();
if (diff != 0) throw "Number of cookies not the same as number of nodes";
return cost;
}
}
// Create tree
let root = new Node(2,
new Node(0,
new Node(0),
new Node(2)
),
new Node(1)
);
console.log(root.transferCost()); // 3轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/380763.html