使二叉树的每个节点都有相等的cookie所需的最小传输成本

Question

给定一个具有n总节点的二叉树，每个节点都有一定数量的cookie，总计n个cookie。

任务是将其转换为具有相同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

我们能用一个最优(时间(算法来解决这个问题吗？

Answer 1

您可以使用后序(深度优先(遍历从每个子树中收集两个信息。定义：

• 偏差：它是预期的cookie数量(即该子树中的节点数量(与该子树中cookie的实际数量之间的差值。如果为负数，则表示cookie不足，并且可以肯定的是，此数量的cookie必须通过该子树的父级来自其他地方。如果是positive，则表示cookie盈余，并且该盈余需要从该子树移到父节点。因此，无论是负数还是正数，它的绝对值都表示子树的根与其父树之间的cookie流。

• 该子树内的转移成本。这表示沿着子树中的边缘移动cookie的成本，既用于填充丢失的cookie，也用于将cookie从具有多个cookie的节点中移出。它还包括向子树的根节点冒泡所有剩余cookie的成本，不包括将它们从那里转移到父节点的成本。它还包括将来自父节点的cookie分发到子树下的成本，但不包括将这些cookie从父节点获取到根节点的成本。

这里存在递归关系。当你有一个给定节点的左子树和右子树的这对信息时，你可以推导出组合树(给定节点是其根(的这一对信息：

• 当前树(植根于给定节点(的偏差是其两个子树的偏差之和，以及当前节点中cookie的数量减1。"；减去1"；反映了在当前节点中拥有1个cookie的目标。

• 当前树(植根于给定节点(的成本是为其两个子树找到的成本和为该节点找到的deviation的绝对值之和(参见前一点(。

下面是一个可运行的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