Skip to content

Problem 5: Decorate Christmas Tree (0 pts)

Problem

Christmas is coming soon. Isla bought a Christmas tree for Tsukasa. A Christmas tree is a Tree instance. There are some gifts on every nodes of the tree, and the label of each node is the number of gifts on it. Every gifts have the same weight.

We say a tree is balanced if it is a leaf or the total weight of its every branches are the same and all its branches are balanced. For example, the left tree is balanced but the right one is not.

3_2

Isla wants to buy more gifts and hang them on the tree to balance it. Please help her implement balance_tree, which takes in a tree t and hangs gifts as few as possible on it to balance it.

Note: For trees which have more than one ways to balance with the same minimum number of gifts, you can choose any one of them as result and it won't influence your score.

圣诞节快到了。Isla 为 Tsukasa 买了一棵圣诞树。一棵圣诞树是一个 Tree 实例。树上的每个节点都有一些礼物，每个节点的 label 是它上面的礼物数量。每件礼物都有相同的重量。

我们说一棵树是平衡的，如果它是叶子节点，或者其每个分支的总重量相同且所有分支都是平衡的。例如，左边的树是平衡的，但右边的不是。

3_2

Isla 想买更多的礼物挂在树上以平衡它。请帮助她实现 balance_tree，它接受一棵树 t，并尽可能少地挂礼物来平衡它。

注意：对于有多种方式用相同的最少礼物数量平衡的树，你可以选择任何一种作为结果，这不会影响你的分数。

def balance_tree(t):
    """Balance a tree.

    >>> t1 = Tree(1, [Tree(2, [Tree(2), Tree(3), Tree(3)]), Tree(2, [Tree(4), Tree(4)])])
    >>> balance_tree(t1)
    >>> t1
    Tree(1, [Tree(2, [Tree(3), Tree(3), Tree(3)]), Tree(3, [Tree(4), Tree(4)])])
    """
    "*** YOUR CODE HERE ***"