Tree类cumulative_mul递归函数子树标签相乘逻辑疑问

问题背景 #

我们需要实现cumulative_mul函数，它会修改Tree实例t，让每个节点的label变成自身label与以该节点为根的所有子树节点label的乘积（即整个子树所有节点的乘积，包含自身）。核心要搞清楚树修改的时机和子树的处理顺序。

Tree类定义 #

class Tree:
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

函数框架及示例 #

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> cumulative_mul(otherTree)
    >>> otherTree
    Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return
    for b in t.branches:
        cumulative_mul(b)
        if isinstance(b, Tree):
            t.label *= b.label

核心困惑 #

能理解递归的大致结构：叶子节点直接返回，子树按层处理后返回自身子树所有节点的乘积。但搞不懂当有多个子树时，这个乘法逻辑具体是怎么运作的？

递归逻辑拆解 #

这个函数用的是后序遍历：先把所有子树处理完，再处理当前节点。我们拿第一个示例t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])一步步拆解：

1. 先钻到最底层的叶子节点

   • 调用cumulative_mul(t)，t不是叶子，进入循环处理第一个分支Tree(3, [Tree(5)])。
   • 递归调用cumulative_mul(Tree(3, [Tree(5)]))，这个节点也不是叶子，处理它的分支Tree(5)。
   • 调用cumulative_mul(Tree(5))，这是叶子节点，直接返回，label保持5不变。

2. 回溯处理父节点Tree(3)

   • 回到Tree(3)的循环，此时Tree(5)已经处理完，它的label就是自己子树（只有自己）的乘积。所以Tree(3)的label = 5 → 35=15。现在Tree(3)的label就变成了它所在子树（自己+叶子5）的总乘积。

3. 处理第二个子树Tree(7)

   • 回到根节点t的循环，处理第二个分支Tree(7)。调用cumulative_mul(Tree(7))，这是叶子，直接返回，label保持7不变。
   • 根节点t的label =7 → 此时根节点的label已经是115=15（之前处理第一个分支时乘过15），再乘7得到1157=105，也就是整个树所有节点的乘积。

多子树的乘法逻辑 #

拿第二个示例里的节点Tree(1, [Tree(3), Tree(4), Tree(5)])来说：

• 先依次处理三个叶子节点3、4、5，它们都直接返回，label不变。
• 然后Tree(1)的label依次乘以3（13=3）、乘以4（34=12）、乘以5（125=60），最终得到1345=60，正好是这个子树所有节点的乘积。

本质上，每个子树处理完成后，它的label就代表了自己子树所有节点的乘积。父节点只需要把自己的初始label，依次和每个子树处理后的label相乘，就能得到以自己为根的整个子树的总乘积。

内容的提问来源于stack exchange，提问作者Proteus Yi