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

Question

给定一棵 二叉树，总共有 n 个节点，每个节点都有一定数量的 cookie，总和为 n 总共 个 cookie.

任务是将其转换为具有相同 cookie 的节点（每个节点 1 个 cookie），并且 最小总传输成本 ，前提是传输成本等于 cookie 的数量在节点之间传输。

Cookie 只能在 a)Parent 至 child b)Child到parent

例子，

在下面的示例中，第一个 cookie 可以从左侧 child 转移到 parent，成本 = 1，然后转移到右侧 child 以使其在所有节点上均等额外成本为 1。因此最低总成本为 2。

    1                   2                1
 2    0     =====>   1     0   =====> 1     1

(given tree)                        (transformed tree)
  
Minimum cost of transfer = 2

我们能有一个最优（时间）算法来解决这个问题吗？

Answer 1

您可以使用post阶（深度优先）遍历从每个子树中收集两个信息。定义：

偏差：它是预期 cookie 数量（即节点数该子树），以及该子树中 cookie 的实际数量。如果为负，则表示 cookie 不足，并且可以肯定的是，这个数量的 cookie 必须通过该子树的父节点来自其他地方。如果 postive，这表示 cookie 盈余，并且该盈余将需要从该子树移出到父节点。所以不管是负的还是正的，它的绝对值代表了这个子树的根和它的父节点之间的cookie流。
该子树中的传输成本。这表示沿子树内边缘移动 cookie 的成本，既可以填充丢失的 cookie，也可以将 cookie 移离具有多个节点的节点。它还包括将所有多余的 cookie 冒泡到子树的根节点的成本，不包括将它们从那里移到父节点的成本。它还包括将来自父节点的 cookie 分发到子树下方的成本，但不包括将这些 cookie 从父节点获取到根节点的成本。

这里有递推关系。当你有给定节点的左右子树的这对信息时，你可以推导出组合树的那对信息（给定节点是根）：

当前树（以给定节点为根）的偏差是它的两个子树的偏差和其中的cookie数量之和当前节点减1。“减1”反映了在当前节点中有1个cookie的目标。
当前树（以给定节点为根）的成本是为其两个子树找到的成本与为该节点找到偏差（参见上一点）。

这是运行nable JavaScript 片段中的一个实现。以下树是运行：

答案是 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

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

Minimum transfer cost required to make every node of binary tree have equal cookies

algorithm

tree

binary

minimum