Lab 7：可变树（Mutable Trees）ok 5 项通过

0. 这份作业在练什么

之前写树的题，用的是函数式的数据抽象：tree(label, branches) 造树， label(t) 和 branches(t) 取值。那套抽象有个硬性限制—— 你没法「改」一棵树，因为 label(t) = 5 这种写法在 Python 里根本不合法 （不能对一个调用表达式赋值）。想让树变样，只能造一棵新的返回出去。

这一讲把树改写成了一个类（class）。Tree 实例有两个实例属性（instance attribute）： t.label 和 t.branches。属性是可以赋值的，于是树就变成了 可变对象（mutable object）。这一个改动带来的连锁反应，才是这份 lab 真正要练的东西：

动手前先确认你会这些

这份 lab 假设你已经掌握：类与实例属性的读写（Lecture 13）、 __repr__ 与 __str__ 的区别（Lecture 14）、 可变树本身（Lecture 15），以及链表 Link （Lecture 16，Q5 需要）。

先把 Tree 类本身读熟，后面每道题都要靠它。这是题面给的完整定义， 和 labs/lab07/lab07.py 里的一字不差：

class Tree:
    """A tree has a label and a list of branches.

    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

    def __repr__(self):
        if self.branches:
            branch_str = ', ' + repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)

    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('  ' + line)
        return [str(self.label)] + lines

几处容易被一眼扫过去、但后面会咬人的细节：

1. Maximum Path Sum

题目要什么

输入一棵树 t，返回「从根走到某个叶子」的所有路径中，路径上标签之和的最大值。

>>> t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)])
>>> max_path_sum(t)
11

翻译成人话：这棵树长这样

1
  5
    1
    3
  10

从根到叶子的完整路径一共三条：1→5→1 和为 7，1→5→3 和为 9，1→10 和为 11。 最大是 11。

要点明的边界情况有两个：

• 路径必须从根开始、到叶子结束。不能中途停下（1→5 不算一条路径）， 也不能从中间某个节点起步。这句话决定了递归的结构。
• 只有一个节点的树（Tree(5)）：唯一的路径就是它自己，答案是 5。 这是 base case。
• 题面没说标签一定是正数。所以不能用「贪心地每步选最大的孩子」这种做法—— 一个小孩子下面可能挂着巨大的子树。也不能用 0 当求最大值的初始值。

怎么想到的

第一个念头往往是：「我得把所有路径都列出来，再挑最大的。」这个念头没错，但直接实现很别扭—— 你得维护一个「当前路径」的列表，一路传下去，到叶子时把和记下来。写得出来，但代码长， 而且它其实在做一件事情两遍：既在遍历，又在累加。

转折点是问自己一个更小的问题：如果我已经知道每个分支的答案，我能不能立刻算出根的答案？

假设 t 的根标签是 1，两个分支分别是 b1（根为 5 的子树）和 b2（就是叶子 10）。 「从 t 的根走到某个叶子」的路径，必然是「先从根迈一步走进某个分支 b， 然后在 b 里从它的根走到某个叶子」。所以：

这就是递归的「信仰之跃」：假装递归调用已经能正确处理小一号的问题，只负责把它拼成大问题的答案。

剩下的问题是：这个式子什么时候会崩？当 t.branches 是空列表时， max([]) 会抛 ValueError: max() arg is an empty sequence。 而 t.branches 为空正好就是叶子。所以叶子必须单独处理——这就是 base case， 而且它的答案我们上面已经想清楚了：叶子的唯一路径就是它自己，返回 t.label。

代码

def max_path_sum(t):
    """Return the maximum path sum of the tree.

    >>> t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)])
    >>> max_path_sum(t)
    11
    """
    if t.is_leaf():
        # A root-to-leaf path that stops here is worth just this label.
        return t.label
    # Otherwise, extend the best path of some branch with the current label.
    return t.label + max([max_path_sum(b) for b in t.branches])

逐行：

• if t.is_leaf(): —— 用方法而不是手写 if not t.branches，两者等价， 但用方法是尊重 Tree 这个抽象。写成 if t.is_leaf（漏括号）会让每棵树都被判成叶子， 返回值直接是根标签，doctest 会显示 1 != 11，从错误信息很难看出是漏了括号。
• return t.label —— base case 返回的是标签本身，不是 0，不是列表。 返回类型必须和递归情形一致（都是数字），否则外层的 + 会炸。
• [max_path_sum(b) for b in t.branches] —— 列表推导式先把每个分支的答案都算出来。 注意这里必须遍历全部分支，不能只看第一个：最大值可能藏在任何一支里。
• max(...) —— 从这些候选里选最大的。因为上一行的 if 已经挡住了叶子， 到这里 t.branches 至少有一个元素，max 不会因空序列报错。
• t.label + ... —— 把当前节点的贡献加上去。加法在最外层， 意味着无论选哪条路径，都必然经过当前节点，这正是「路径从根开始」的含义。

另外注意这个函数没有修改任何东西。虽然这一讲主题是可变树， 但 Q1 是纯查询，不该动 t。能不改就不改，是写可变数据结构时的基本纪律。

验证

拿 doctest 里的 t = Tree(1, [Tree(5, [Tree(1), Tree(3)]), Tree(10)]) 真的展开一遍。 为了写起来清楚，给节点起名：根叫 A（label 1）， A 的两个分支是 B（label 5）和 E（label 10）， B 的两个分支是 C（label 1）和 D（label 3）。

max_path_sum(A)                       A 不是叶子（有 B、E）
└─ 需要 max([max_path_sum(B), max_path_sum(E)])
   ├─ max_path_sum(B)                 B 不是叶子（有 C、D）
   │  └─ 需要 max([max_path_sum(C), max_path_sum(D)])
   │     ├─ max_path_sum(C)           C 是叶子 → return 1
   │     └─ max_path_sum(D)           D 是叶子 → return 3
   │     max([1, 3]) = 3
   │     return 5 + 3 = 8
   └─ max_path_sum(E)                 E 是叶子 → return 10
   max([8, 10]) = 10
   return 1 + 10 = 11

最终返回 11，与 doctest 一致。

顺带看清楚一件事：max_path_sum(B) 返回的 8 代表路径 5→3， 它不含根节点的 1。每一层递归返回的都是「以我为起点」的答案，加根标签的动作发生在回代时。 把这个「谁负责加自己」搞清楚，后面所有树递归都不会乱。

2. Add Leaves

题目要什么

定义节点的深度（depth）为从根到该节点的边数，根的深度是 0。 add_d_leaves(t, v) 要求：对树里的每个节点，给它加上 d 片叶子， 其中 d 是这个节点的深度，每片新叶子的标签都是 v。 如果这个节点本来就有分支，新叶子加在分支列表的末尾。

也就是说：深度 1 的节点各加 1 片叶子，深度 2 的各加 2 片，深度 0 的根加 0 片（等于不加）。

这个函数没有返回值——它是就地修改（mutate）t。doctest 里 >>> add_d_leaves(t_one_to_four, 5) 那行下面什么都没有， 就是在告诉你「返回 None」。写成 return t 会让 doctest 直接失败。

>>> t_one_to_four = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> print(t_one_to_four)
1
  2
  3
    4
>>> add_d_leaves(t_one_to_four, 5)
>>> print(t_one_to_four)
1
  2
    5
  3
    4
      5
      5
    5

对着这个例子核一遍：节点 1 深度 0，加 0 片；节点 2 和 3 深度 1，各加 1 片 （2 底下多了一个 5；3 的分支列表末尾多了一个 5，排在原有的 4 后面）； 节点 4 深度 2，加 2 片。完全对上。

两个致命的边界情况，题面用 Hint 明说了：

怎么想到的

第一步：递归形状是什么？

「对树里的每个节点做点事」——这是最标准的树遍历。骨架一定长这样：

def f(t):
    对 t 自己做点事
    for b in t.branches:
        f(b)

第二步：卡在深度上。

「做点事」是「加 d 片叶子」，可 d 是多少？在 f(t) 内部，光看着 t 这个对象， 是看不出它在整棵树里有多深的——Tree 实例里没有指向父节点的指针， 它只知道自己的 label 和 branches。深度是「从外面看」才有的信息。

那就把它从外面传进来。定义一个多带一个参数的辅助函数 add_leaves(t, d)， 含义是「t 这个节点的深度是 d，请给它加 d 片叶子，并且它的每个孩子深度是 d+1」。 最外层调用 add_leaves(t, 0)，因为传进来的 t 就是整棵树的根，深度 0。

第三步：踩 Hint 2 的坑。

最自然的写法是「先做自己，再做孩子」：

def add_leaves(t, d):        # 错误版本
    t.branches.extend([Tree(v) for _ in range(d)])
    for b in t.branches:
        add_leaves(b, d + 1)

拿 Tree(1, [Tree(2), Tree(3, [Tree(4)])]) 跑一下就知道错在哪。 add_leaves(节点2, 1) 先给节点 2 加了一片叶子 Tree(5)， 于是 节点2.branches == [Tree(5)]；接着 for b in t.branches 开始遍历， 第一个（也是唯一一个）b 就是刚加进去的那片 Tree(5)， 于是调用 add_leaves(Tree(5), 2)——给它加 2 片新叶子，然后又去遍历这 2 片新叶子， 给每片加 3 片……每一层都会造出更多节点，永远到不了 base case。 真实报错是：

RecursionError: maximum recursion depth exceeded

这就是 Hint 2 说的「只给原有节点加叶子」。怎么办？两条路：

B 更短也更干净，一个字符的额外空间都不用。我们采用 B。 注意 B 之所以成立，是因为「给 t 加叶子」和「处理 t 的孩子」这两件事互不依赖—— 加叶子不影响孩子该加几片，处理孩子也不影响 t 该加几片。顺序可以自由交换， 那就选一个不会自己咬自己的顺序。

代码

def add_d_leaves(t, v):
    """Add d leaves containing v to each node at every depth d."""
    def add_leaves(t, d):
        """Add d leaves to t, d + 1 leaves to each branch of t, and so on."""
        # Recurse into the ORIGINAL branches first, so the leaves we are about
        # to append below never receive leaves of their own.
        for b in t.branches:
            add_leaves(b, d + 1)
        t.branches.extend([Tree(v) for _ in range(d)])
    add_leaves(t, 0)

（上面省略了长长的 docstring，完整版见 labs/lab07/lab07.py。）逐行：

• def add_leaves(t, d): —— 内部参数也叫 t，把外层的 t 遮住了（shadow）。 这没问题，因为 add_leaves 里再也用不到外层那个 t；每次递归调用都会创建新的帧， 帧里的 t 绑定到当前子树。
• for b in t.branches: add_leaves(b, d + 1) —— 孩子的深度比自己大 1。 这行必须在 extend 之前，理由见上。
• [Tree(v) for _ in range(d)] —— 造 d 个互相独立的叶子。 用 _ 当循环变量是惯例，表示「这个值我不关心，我只要循环 d 次」。 关键是每次循环都调一次 Tree(v)，得到 d 个不同的对象。 写成 [Tree(v)] * d 就完全错了：那是同一个对象重复 d 次， 后续对其中任何一个的修改会同时反映在另外 d-1 个位置上。
• t.branches.extend(...) —— extend 是原地修改列表， 把新元素一个个追加到末尾，正好符合题目「加在末尾」的要求，返回 None。 如果写成 t.branches = t.branches + [...]，效果在这里也一样 （因为是给实例属性重新赋值，仍然改到了 t）；但如果写成 t.branches.append([Tree(v) for _ in range(d)]) 就错了—— append 会把整个列表当成一个元素塞进去， 于是 t.branches 里混进了一个 list 而不是 Tree， 下次递归时 b.branches 会报 AttributeError: 'list' object has no attribute 'branches'。
• d == 0 时 range(0) 是空的，列表推导式给出 []， extend([]) 什么也不做。所以根节点自动不加叶子，不需要写 if。
• add_leaves(t, 0) —— 唯一的顶层调用，深度从 0 起。 add_d_leaves 本身没有 return，自动返回 None，符合 doctest。

验证

先用第一个 doctest 完整追一遍。给节点起名： A=Tree(1)，它的分支是 B=Tree(2) 和 C=Tree(3)，C 的分支是 D=Tree(4)。

add_leaves(A, 0)
├─ for b in A.branches → [B, C]
│  ├─ add_leaves(B, 1)
│  │  ├─ for b in B.branches → []   循环体不执行（隐式 base case）
│  │  └─ B.branches.extend([Tree(5)])        B.branches = [5]
│  └─ add_leaves(C, 1)
│     ├─ for b in C.branches → [D]
│     │  └─ add_leaves(D, 2)
│     │     ├─ for b in D.branches → []
│     │     └─ D.branches.extend([Tree(5), Tree(5)])   D.branches = [5, 5]
│     └─ C.branches.extend([Tree(5)])        C.branches = [D, 5]
└─ A.branches.extend([])                     A.branches = [B, C] 不变

注意 C.branches.extend 发生在 add_leaves(D, 2) 之后： 此时 D 已经带上了自己的两片叶子，而新加到 C 后面的那片 5 是全新的、 再也没人会去动它。这正是「先递归后追加」的意义。print(A) 得到：

1
  2
    5
  3
    4
      5
      5
    5

与 doctest 一致。

别名：doctest 里的 t3 到底发生了什么

第二组 doctest 才是这道题真正的考点。它是这样铺垫的：

>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])

第一步：t1 原本是 Tree(1, [Tree(3)])， 调用 add_d_leaves(t1, 4) 之后，深度 1 的节点 Tree(3) 被加了 1 片标签为 4 的叶子， 所以 t1 已经被永久改成了 Tree(1, [Tree(3, [Tree(4)])])。 后面再用到 t1，用的都是改过之后的版本。

第二步：t3 = Tree(3, [t1, Tree(0), t2])。 Tree.__init__ 里的 self.branches = list(branches) 只做了浅拷贝： 新建了一个列表，但列表里第 0 个元素就是 t1 本人，第 2 个元素就是 t2 本人。 画出来是这样：

名字          对象
------------------------------------------------------
t1  ─────────▶ Tree#1  label=1  branches=[Tree#2]
                        Tree#2  label=3  branches=[Tree#3]
                        Tree#3  label=4  branches=[]

t2  ─────────▶ Tree#4  label=2  branches=[Tree#5, Tree#6]

t3  ─────────▶ Tree#7  label=3  branches=[ Tree#1, Tree#8, Tree#4 ]
                                             ▲               ▲
                                             │               │
                                        就是 t1          就是 t2
                                    （不是拷贝！）    （不是拷贝！）

所以 t3.branches[0] is t1 求值为 True。 接下来 add_d_leaves(t3, 10) 会顺着 t3.branches[0] 递归下去， 改的就是 t1 指向的那个对象。调用完之后 t1 也变了， 虽然代码里从头到尾没出现过 t1 这个名字。这就是别名的威力，也是它的危险之处。

Tree#7  label=3   d=0   加 0 片
├─ Tree#1  label=1   d=1   加 1 片        ← 就是 t1
│  └─ Tree#2  label=3   d=2   加 2 片
│     └─ Tree#3  label=4   d=3   加 3 片
├─ Tree#8  label=0   d=1   加 1 片
└─ Tree#4  label=2   d=1   加 1 片        ← 就是 t2
   ├─ Tree#5  label=5   d=2   加 2 片
   └─ Tree#6  label=6   d=2   加 2 片

print(t3) 的结果：

3
  1
    3
      4
        10
        10
        10
      10
      10
    10
  0
    10
  2
    5
      10
      10
    6
      10
      10
    10

一行一行对：4 底下三个 10（d=3），3 底下在 4 这一支之后有两个 10（d=2）， 1 底下在 3 这一支之后有一个 10（d=1），0 底下一个 10（d=1）， 5 和 6 各两个 10（d=2），2 最后一个 10（d=1）。与 doctest 完全一致。

还有两个小 doctest 值得一提：t0 = Tree(9)，add_d_leaves(t0, 4) 之后 t0 仍是 Tree(9)。因为根的深度是 0，加 0 片。 这个用例专门验证你没有把「根也算深度 1」搞错，也验证了单节点树不会崩。

3. Has Path

题目要什么

has_path(t, target)：t 是一棵每个节点标签都恰好是一个字符的树， target 是一个字符串。问：树里存不存在一条从根出发的路径， 把路径上的字符依次拼起来正好等于 target？是就返回 True，否则 False。

题面还告诉你这个结构叫 trie（前缀树），自动补全就是靠它实现的。

>>> greetings = Tree('h', [Tree('i'),
...                        Tree('e', [Tree('l', [Tree('l', [Tree('o')])]),
...                                   Tree('y')])])
>>> print(greetings)
h
  i
  e
    l
      l
        o
    y
>>> has_path(greetings, 'h')
True
>>> has_path(greetings, 'i')
False
>>> has_path(greetings, 'hi')
True
>>> has_path(greetings, 'hello')
True
>>> has_path(greetings, 'hey')
True
>>> has_path(greetings, 'bye')
False
>>> has_path(greetings, 'hint')
False

这七个 doctest 每一个都在考一件不同的事，值得逐条读：

另外函数开头给了 assert len(target) > 0, 'no path for empty target.'， 这行是题目给好的，意思是空字符串不是合法输入，你不用为它设计行为。 这很重要——它把「target 用完了」这种状态从可能性里排除了， 所以你的 base case 应该是「target 只剩 1 个字符」，而不是「target 变成空串」。

怎么想到的

第一步：识别出这是「两个东西同时缩小」的递归。

树的题目通常只有树在缩小。这道题有两个参数，而且它们同步缩小： 每往下走一层，树变成某个子树，target 就少掉开头一个字符。 一旦看出这一点，递归调用的形状就定了：has_path(b, target[1:])。

第二步：想清楚每一步该检查什么。

站在某个节点 t 上，手里拿着一个还没匹配的字符串 target， 我要回答的问题是：「从 t 出发能不能拼出 target？」 （注意递归调用时语义保持一致，所以「从根出发」这个约束在每一层都自动成立。）

第三步：确认叶子的情况被覆盖了。

这是最容易漏的一环。当 t 是叶子而 target 还剩不止一个字符时会怎样？ 第 1 步过了（label 对上），第 2 步不成立（len(target) > 1）， 第 3 步的 for b in t.branches 遍历空列表，循环体一次也不执行，直接落到最后的 return False。正确。这正是 has_path(greetings, 'hint') 的情形： 走到 i 时手里还剩 'int'，i 是叶子，无路可走，返回 False。

代码

def has_path(t, target):
    """Return whether there is a path in a Tree where the entries along the path
    spell out a particular target."""
    assert len(target) > 0, 'no path for empty target.'
    if t.label != target[0]:
        # The path must start at the root, so the first letter has to match.
        return False
    if len(target) == 1:
        # Matched the whole target; the path may stop here.
        return True
    # Look for the rest of the target starting at any branch.
    for b in t.branches:
        if has_path(b, target[1:]):
            return True
    return False

逐行：

• assert len(target) > 0, ... —— 题目给的，别删。它保证了下一行的 target[0] 不会因为空串报 IndexError。注意 assert 在递归调用里每层都会执行一次， 所以它同时也保证了你不会写出 has_path(b, '') 这种调用——如果写了， 会立刻触发 AssertionError: no path for empty target.， 这个报错反而是在提醒你 base case 设计错了。
• if t.label != target[0]: return False —— 用「不匹配就早退」的写法（guard clause）， 比写成一个大 if t.label == target[0]: 再嵌套三层要清爽得多。 target[0] 是长度为 1 的字符串，t.label 也是单字符字符串， 两者用 != 比较是字符串比较，没问题。
• if len(target) == 1: return True —— base case。 能走到这行说明第一个字符已经匹配，而且它是最后一个字符。
• for b in t.branches: —— 这里必须遍历所有分支， 因为不知道正确的路走哪边。'hey' 那个用例里， 在节点 e 处第一个分支是 l，试了不行，还得回来试 y。 这种「试一条，不行就换一条」的模式叫回溯（backtracking）。
• if has_path(b, target[1:]): return True —— 一旦找到就立刻返回， 不再试剩下的分支（短路）。写成 return has_path(b, target[1:])（少了 if） 是最常见的错误：那样只会试第一个分支，第一个不行就直接返回 False 了， 'hey' 会挂。
• target[1:] —— 字符串切片，从下标 1 到末尾。 当 len(target) == 2 时它是长度 1 的串，不是空串，因为 len(target) == 1 的情况 在上面已经返回了，能走到这里说明 len(target) >= 2，切完至少还剩 1 个字符。 所以下一层的 assert 一定不会触发。
• return False —— 循环正常结束（没有任何分支成功），或者压根没有分支（叶子）。 这行必须在循环外面。放进循环里（else: return False 缩在 for 内） 会导致第一个分支失败就整体返回 False，同样挂掉 'hey'。

for b in t.branches:            # 版本 1（本题采用）
    if has_path(b, rest):
        return True
return False

return any(has_path(b, rest) for b in t.branches)   # 版本 2

return True in [has_path(b, rest) for b in t.branches]  # 版本 3（会算完所有分支，不短路）

验证

先追 has_path(greetings, 'hey')。节点命名： H=Tree('h')，它的分支是 I=Tree('i') 和 E=Tree('e')， E 的分支是 L1=Tree('l') 和 Y=Tree('y')。

has_path(H, 'hey')
  H.label='h' == 'h'          ✓ 继续
  len('hey')=3 ≠ 1            继续找分支
  ├─ has_path(I, 'ey')
  │    I.label='i' != 'e'     ✗ return False
  └─ has_path(E, 'ey')
       E.label='e' == 'e'     ✓ 继续
       len('ey')=2 ≠ 1        继续找分支
       ├─ has_path(L1, 'y')
       │    L1.label='l' != 'y'  ✗ return False
       └─ has_path(Y, 'y')
            Y.label='y' == 'y'   ✓
            len('y')==1          → return True
       某个分支返回 True    → return True
  某个分支返回 True         → return True

结果 True。注意 has_path(I, 'ey') 失败之后，循环继续试 E—— 这就是回溯。同样，在 E 这一层，L1 失败之后继续试 Y。 如果代码里写的是 return has_path(b, target[1:])， 第一次调用就会在 has_path(I, 'ey') 返回 False 后把 False 一路传上去， 最终输出 False != True。

再追一个 False 的：has_path(greetings, 'hint')。

has_path(H, 'hint')
  'h' == 'h'  ✓ ；len=4 ≠ 1
  ├─ has_path(I, 'int')
  │    I.label='i' == 'i'   ✓
  │    len('int')=3 ≠ 1     继续找分支
  │    for b in I.branches → []   一次都不循环
  │    → return False              ← 叶子挡住了去路
  └─ has_path(E, 'int')
       E.label='e' != 'i'   ✗ return False
  循环结束，没有 True → return False

结果 False。这个例子把「隐式 base case」演示得最清楚： 函数里没有一行写着 if t.is_leaf()，但叶子的行为完全正确—— 空的 branches 让 for 循环退化成空操作，自然掉进最后的 return False。

最后确认最短的用例 has_path(greetings, 'h')： 'h' == 'h' 通过，len('h') == 1 成立，立刻 return True。 一次递归都没发生。而 has_path(greetings, 'i')： H.label 是 'h'，target[0] 是 'i'，第一行判断就返回 False。

4. Preorder

题目要什么

preorder(t) 返回一个列表，装着树里所有标签， 顺序是「print(t) 打印时它们出现的先后顺序」。这个顺序有个正式名字叫 先序遍历（preorder traversal）。

>>> numbers = Tree(8, [Tree(2), Tree(9, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
>>> print(numbers)
8
  2
  9
    4
    5
  6
    7
>>> preorder(numbers)
[8, 2, 9, 4, 5, 6, 7]

「先序」这个词的含义是：先访问自己，再依次访问每个分支（从左到右）， 每个分支内部也遵循同样的规则。对照打印结果：先 8（根）， 然后第一个分支只有 2；然后第二个分支 9，进去先 9 自己，再 4、5； 然后第三个分支 6，先 6 自己，再 7。串起来正是 [8, 2, 9, 4, 5, 6, 7]。

边界情况：单节点树 Tree(5) 应返回 [5]——一个只含根标签的列表， 不是 5，也不是 []。返回类型必须始终是列表。

def indented(self):
    lines = []
    for b in self.branches:
        for line in b.indented():
            lines.append('  ' + line)
    return [str(self.label)] + lines

怎么想到的

第一步：确定返回类型，并让它在递归中保持一致。

这是所有「返回列表」型递归题的第一件事。preorder(t) 返回列表， 那么 preorder(b) 也返回列表。于是问题变成： 已知每个分支的标签列表，怎么拼出整棵树的标签列表？

第二步：把「先序」的定义直接翻译成拼接顺序。

先序 = 自己在最前，然后按左到右接上每个分支的先序结果。写成式子就是：

preorder(t) = [t.label] + preorder(b1) + preorder(b2) + ... + preorder(bn)

第三步：检查 base case。

叶子的 t.branches 是空列表，循环不执行，直接返回 [t.label]——正是我们要的。 所以又是一个不需要写显式 base case 的遍历型递归。 这已经是这份 lab 里第三次出现同一个套路了（Q2、Q3、Q4）， 可以把它当成一条规律记下来：只要递归结果是「靠 for 循环累积起来的」， 叶子就会被 for 循环自动兜住。

代码

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = Tree(8, [Tree(2), Tree(9, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> preorder(numbers)
    [8, 2, 9, 4, 5, 6, 7]
    """
    labels = [t.label]          # visit the root first
    for b in t.branches:
        labels += preorder(b)   # then each branch, left to right
    return labels

逐行：

• labels = [t.label] —— 注意方括号。写成 labels = t.label 会让 labels 变成一个整数，下一行 labels += preorder(b) 报 TypeError: unsupported operand type(s) for +=: 'int' and 'list'。 「自己排最前面」这一步在这里就完成了，不用等到最后。
• for b in t.branches: —— 列表的迭代顺序就是从左到右， 正好对应「按分支顺序访问」。这里不需要 sorted 或反转。
• labels += preorder(b) —— += 作用在列表上等价于 labels.extend(preorder(b))，是原地把右边列表的每个元素追加到 labels 末尾。 关键在于加的是「元素」不是「列表本身」。 如果写成 labels.append(preorder(b))，得到的是嵌套列表 [8, [2], [9, 4, 5], [6, 7]]，doctest 会明确显示这个结果，一眼能看出问题。
• return labels —— 必须在 for 循环外面。 缩进到循环里面的话，第一个分支处理完就返回了， preorder(numbers) 会得到 [8, 2]。这是最常见的缩进错误。

def preorder(t, acc=[]):     # 危险！
    acc.append(t.label)
    for b in t.branches:
        preorder(b, acc)
    return acc

验证

把 numbers 的节点命名：R=Tree(8)； 它的三个分支是 P=Tree(2)、Q=Tree(9)、S=Tree(6)； Q 的分支是 U=Tree(4)、V=Tree(5)；S 的分支是 W=Tree(7)。

preorder(R)
  labels = [8]
  ├─ b = P: preorder(P)
  │           labels = [2]；P.branches 为空，循环不执行
  │           return [2]
  │  labels = [8] + [2] = [8, 2]
  ├─ b = Q: preorder(Q)
  │           labels = [9]
  │           ├─ preorder(U) → [4]      labels = [9, 4]
  │           └─ preorder(V) → [5]      labels = [9, 4, 5]
  │           return [9, 4, 5]
  │  labels = [8, 2] + [9, 4, 5] = [8, 2, 9, 4, 5]
  └─ b = S: preorder(S)
              labels = [6]
              └─ preorder(W) → [7]      labels = [6, 7]
              return [6, 7]
     labels = [8, 2, 9, 4, 5] + [6, 7] = [8, 2, 9, 4, 5, 6, 7]
  return [8, 2, 9, 4, 5, 6, 7]

与 doctest 的 [8, 2, 9, 4, 5, 6, 7] 一致。

对照 print(numbers) 的输出，把每一行的标签从上往下抄下来， 得到的正是同一个序列。这不是巧合：indented 和 preorder 是同一个遍历顺序， 前者把结果拼成带缩进的字符串，后者把结果收进列表。

顺便：先序、后序、层序的区别

这道题只要先序，但把三种顺序放一起对比能帮你记住「递归里的一行代码放在循环前还是循环后， 决定了访问顺序」：

注意先序和后序的差别，在代码上只是「把自己的标签放进 labels」这一句 放在 for 循环之前还是之后。Q2 的「先递归后 extend」其实也是同一类判断： 在树递归里，一句话摆在循环前还是循环后，往往不是风格问题，而是语义问题。

5. Level Mutation Link

题目要什么

给一棵树 t 和一个装着单参数函数的链表 funcs， 用 funcs 里的函数就地修改 t 的标签，深度和位置一一对应：

• 深度 0 的节点（根）用 funcs.first 处理；
• 深度 1 的节点用 funcs.rest.first 处理；
• 深度 2 的用 funcs.rest.rest.first，以此类推。

「处理」的意思是 t.label = 那个函数(t.label)。两条特殊规则：

>>> t = Tree(1, [Tree(2, [Tree(3)])])
>>> funcs = Link(lambda x: x + 1, Link(lambda y: y * 5, Link(lambda z: z ** 2)))
>>> level_mutation_link(t, funcs)
>>> t
Tree(2, [Tree(10, [Tree(9)])])
>>> t2 = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> level_mutation_link(t2, funcs)
>>> t2
Tree(2, [Tree(100), Tree(15, [Tree(16)])])
>>> t3 = Tree(1, [Tree(2)])
>>> level_mutation_link(t3, funcs)
>>> t3
Tree(2, [Tree(100)])

三个 doctest 恰好覆盖三种情况，逐个读懂它们是做出这题的前提：

特别注意 t2 这个用例：同一个深度上，叶子和非叶子的待遇不同。 Tree(2) 和 Tree(3) 都在深度 1，都先被 y*5 处理， 但只有叶子的那个会继续吃掉后面所有函数。这是整道题最容易写错的地方。

还要注意：这题的模板是填空形式，骨架已经给定，你要顺着它的结构想。 另外注意 funcs 在三次调用之间没有被重新创建—— 所以你的函数绝不能修改 funcs 这个链表本身（比如 funcs.rest = ...）， 否则第二个 doctest 就会用到被破坏的 funcs。

先复习 Link

Q5 需要 Link 类，它的定义在 lab07.py 末尾：

class Link:
    """A linked list."""
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

要点：Link.empty 是一个类属性，值是空元组 ()。 判断链表是否为空，惯例写 is Link.empty 而不是 == Link.empty—— 用 is 比的是「是不是同一个对象」，这里正是我们要的意思， 而且 Link 类没有定义 __eq__，用 == 在这个特定实现下也能工作， 但 is 表达的意图更准确、也是课程约定。

这张表解释了为什么本题的代码里既有 while 又有 for： 沿链表往后走是线性的，用 while；沿树往下走会分叉，用 for 加递归。

怎么想到的

第一步：认出「两个结构同步推进」。

这和 Q3 是同一个母题。Q3 里树往下走一层、字符串砍掉一个字符； 这里树往下走一层、链表往后挪一格。递归调用必然是 level_mutation_link(b, funcs.rest) 这个形状—— 深度这个信息不需要显式传，它已经编码在「funcs 走到哪儿了」里面。 这比 Q2 用辅助函数带 d 更巧：因为 funcs 本身就是按深度排好的。

第二步：base case 是链表空了，不是树到底了。

规则 B 说得很明白：funcs 空了树就不动。所以第一行必然是 if funcs is Link.empty: return。注意是 return 不是 return something—— 这个函数靠副作用工作，返回 None。

反过来，树到底了（叶子）不是 base case，因为规则 A 说叶子还要继续干活。

第三步：处理规则 A。

先把当前这一层该做的事做掉：t.label = funcs.first(t.label)。 然后 remaining = funcs.rest 是「留给孩子们的函数」。

如果 t 有孩子，把 remaining 传下去就行。 如果 t 是叶子，没有孩子来接手 remaining， 按规则 A 就得自己把它们全用了。链表是线性的，用一个 while 循环挨个走：

while remaining is not Link.empty:
    t.label = remaining.first(t.label)
    remaining = remaining.rest

每轮把 t.label 喂给当前函数、结果存回 t.label，然后链表指针往后挪一格。 顺序很重要：题目说「按顺序作用」，所以是 y*5 先、z**2 后， 2 → 10 → 100；反过来就是 2 → 4 → 20，错。

第四步：确认最后那个 for 循环不会出事。

骨架的最后是 for b in t.branches:，它写在 if t.is_leaf(): 的外面。 乍看有点怪：叶子分支里 remaining 被 while 循环改成了 Link.empty， 那后面的 for 循环用的岂不是被改坏的 remaining？

不会出事——因为进入 while 循环的前提是 t.is_leaf() 为真， 而叶子的 t.branches 是空列表，for 循环一次都不执行。 两条路互斥：要么走 while（叶子，没有 for 可跑），要么跳过 while（非叶子，remaining 原封不动）。 所以把 for 放在最外面是安全的，而且省掉了一个 else。

代码

def level_mutation_link(t, funcs):
	"""Mutates t using the functions in the linked list funcs."""
	if funcs is Link.empty:
		return
	t.label = funcs.first(t.label)
	remaining = funcs.rest
	if t.is_leaf():
		while remaining is not Link.empty:
			t.label = remaining.first(t.label)
			remaining = remaining.rest
	for b in t.branches:
		level_mutation_link(b, remaining)

（这道题的模板用的是 Tab 缩进而不是 4 空格，上面保持了原样。 Python 不允许在同一个代码块里混用 Tab 和空格，你在填空时要跟着模板走， 否则会报 TabError: inconsistent use of tabs and spaces in indentation。）

逐行：

• if funcs is Link.empty: return —— 规则 B。 既是 base case，也保护了下一行：如果 funcs 是 ()， funcs.first 会报 AttributeError: 'tuple' object has no attribute 'first'。
• t.label = funcs.first(t.label) —— 这一行有两层含义。 funcs.first 不是一个数，而是一个函数对象（doctest 里是 lambda）， 所以 funcs.first(t.label) 是一次函数调用。 把结果赋回 t.label 就完成了对树的就地修改——这是整道题唯一真正「改树」的地方 （下面 while 里那行是同一件事的重复）。
• remaining = funcs.rest —— 给「剩下的函数」起个名字。 不能写成 funcs = funcs.rest：那样虽然也能跑（只是重绑局部名字，不会影响调用者）， 但会让后面 if t.is_leaf() 里的逻辑读起来混乱。起个新名字表达「这是留给下一层的」。
• if t.is_leaf(): —— 规则 A 的触发条件。
• while remaining is not Link.empty: —— 沿链表走到底。 用 is not 而不是 !=，和 is Link.empty 对称。
• t.label = remaining.first(t.label) —— 把当前标签喂给当前函数，结果存回去。 注意右边用的是刚更新过的 t.label，所以函数是依次复合的： f2(f1(label))，而不是各算各的。
• remaining = remaining.rest —— 循环变量推进。忘了这行就是死循环， 程序卡住不返回。这是链表 while 循环最经典的错误。
• for b in t.branches: level_mutation_link(b, remaining) —— 每个孩子都拿到同一个 remaining。 这体现了「同一深度用同一个函数」：三个孩子都在深度 d+1，都该用 funcs.rest.first。 不能写成 level_mutation_link(b, remaining.rest)（跳了一级）， 也不能在循环里更新 remaining（那会让不同的孩子用不同的函数）。

验证

用第二个 doctest（最能体现规则 A）完整追一遍。记 f1 = lambda x: x + 1、f2 = lambda y: y * 5、f3 = lambda z: z ** 2， funcs = Link(f1, Link(f2, Link(f3)))。 树 t2 = Tree(1, [Tree(2), Tree(3, [Tree(4)])])， 节点命名 A=Tree(1)、B=Tree(2)、C=Tree(3)、D=Tree(4)。

level_mutation_link(A, Link(f1, Link(f2, Link(f3))))
  funcs 非空
  A.label = f1(1) = 1 + 1 = 2                    A: 1 → 2
  remaining = Link(f2, Link(f3))
  A.is_leaf()? 否（有 B、C）→ 跳过 while
  for b in [B, C]:

  ├─ level_mutation_link(B, Link(f2, Link(f3)))
  │    funcs 非空
  │    B.label = f2(2) = 2 * 5 = 10               B: 2 → 10
  │    remaining = Link(f3)
  │    B.is_leaf()? 是 → 进入 while
  │      第 1 轮: remaining = Link(f3) 非空
  │               B.label = f3(10) = 10 ** 2 = 100    B: 10 → 100
  │               remaining = Link.empty
  │      第 2 轮: 条件为假，退出
  │    for b in B.branches → []  不执行
  │
  └─ level_mutation_link(C, Link(f2, Link(f3)))
       funcs 非空
       C.label = f2(3) = 3 * 5 = 15               C: 3 → 15
       remaining = Link(f3)
       C.is_leaf()? 否（有 D）→ 跳过 while
       for b in [D]:
       └─ level_mutation_link(D, Link(f3))
            funcs 非空
            D.label = f3(4) = 4 ** 2 = 16         D: 4 → 16
            remaining = Link.empty
            D.is_leaf()? 是 → while 条件立刻为假，不执行
            for b in D.branches → []  不执行

最终 A.label=2、B.label=100、C.label=15、D.label=16， 所以 t2 显示为 Tree(2, [Tree(100), Tree(15, [Tree(16)])])，与 doctest 一致。

请重点对比 B 和 C：它们深度相同、拿到的 funcs 是同一个 Link(f2, Link(f3))，前两行代码走得一模一样（都做了 *5）。 分岔发生在 is_leaf()：B 没有孩子，只好自己把 f3 用掉； C 有孩子，就把 f3 原封不动交给 D。

再快速核第三个 doctest：t3 = Tree(1, [Tree(2)])。 根做 f1：1 → 2，remaining = Link(f2, Link(f3))，非叶子，传给 Tree(2)。 Tree(2) 先做 f2：2 → 10，remaining = Link(f3)； 它是叶子，while 把 f3 也用上：10 → 100。 结果 Tree(2, [Tree(100)])，正确。

6. 附：tests/ 目录里的两份概念题

先说明一件事，免得你困惑：labs/lab07/tests/ 下有两个文件 inheritance-abc.py 和 link.py，它们是 WWPD（What Would Python Display） 类型的概念题。跑 python3 ok --local 时输出的是 5 test cases passed——这 5 项就是上面五道编程题的 doctest， 这两份概念题在 lab07.ok 里没有列进 default_tests， 标注也是 'points': 0、'scored': False，不计分。 但它们考的东西（类属性查找、链表语义）恰好是这份 lab 的地基，值得单独讲清楚。

Inheritance ABCs：类属性到底存在哪儿

>>> class A:
...   x, y = 0, 0
...   def __init__(self):
...         return
>>> class B(A):
...   def __init__(self):
...         return
>>> class C(A):
...   def __init__(self):
...         return

A 有两个类属性（class attribute） x 和 y，都是 0。 B 和 C 都继承 A，自己什么属性都没定义。 关键的一句话是：属性查找沿继承链向上走，但赋值永远只写在被赋值的那个对象上。

>>> print(A.x, B.x, C.x)
0 0 0

只有 A 自己有 x。求 B.x 时 Python 先在 B 的属性表里找， 没找到，就到父类 A 里找，找到 0。C.x 同理。所以三个都是 0， 但要清楚它们是同一个 0，来自同一处存储。

>>> B.x = 2
>>> print(A.x, B.x, C.x)
0 2 0

这一步是全题的核心。B.x = 2 不会去改 A 里的 x—— 赋值语句从不「顺着继承链找地方写」，它直接在 B 自己的属性表里 新建一个名为 x 的条目，值为 2。 从此 B 有了自己的 x，把父类的遮住（shadow）了。 A.x 仍是 0，C 依旧没有自己的 x、继续从 A 拿到 0。

B.x = 2 之前                       B.x = 2 之后
--------------------------        --------------------------
A: {x: 0, y: 0, __init__}         A: {x: 0, y: 0, __init__}
B: {__init__}          ──▶ A      B: {x: 2, __init__}    ──▶ A
C: {__init__}          ──▶ A      C: {__init__}          ──▶ A

B.x 查到 A 里的 0                  B.x 查到 B 自己的 2，不再上溯

>>> A.x += 1
>>> print(A.x, B.x, C.x)
1 2 1

A.x += 1 展开是 A.x = A.x + 1，即 A.x = 0 + 1 = 1， 写在 A 自己身上。B 已经有了自己的 x = 2，不受影响。 C 没有自己的 x，还是向上找，于是跟着变成 1。 「跟着变」的前提是从来没被单独赋过值，这是最容易搞混的一点。

>>> obj = C()
>>> obj.y = 1
>>> C.y == obj.y
False

同样的规则再演一遍，只是这次多了一层：实例。 obj.y = 1 在实例 obj 自己的属性表里建了个 y， 类 C（以及 A）完全不知情。 所以 C.y 还是从 A 继承来的 0，而 obj.y 是 1，0 == 1 为 False。

>>> A.y = obj.y
>>> print(A.y, B.y, C.y, obj.y)
1 1 1 1

A.y = obj.y 先求右边得到 1，再写进 A。现在： A.y 是 1（自己的）；B.y、C.y 都没有自己的 y， 向上找到 A 的 1；obj.y 是它自己的 1。四个都打印 1， 但来源有三处——这一点在下次考试里几乎一定会考。

Link：三个值得看的用例

>>> link = Link(1000, 2000)
Error
>>> link = Link(1000, Link())
Error

第一个报错来自 __init__ 里的 assert rest is Link.empty or isinstance(rest, Link)： 2000 既不是 () 也不是 Link 实例，触发 AssertionError。 这个断言的作用是守住数据抽象——链表的 rest 只能是链表或空。 第二个报错不一样：Link() 少了必需的 first 参数， 是 TypeError: __init__() missing 1 required positional argument: 'first'， 在断言之前就炸了。空链表不是 Link()，而是 Link.empty。

>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty
False
>>> link.rest.rest.rest.rest.first
1

link.rest = link 让这个节点的 rest 指向它自己， 造出一个环。于是 link.rest 就是 link， link.rest.rest 还是 link，无论点多少次 .rest 都是同一个对象， .first 永远是 1，永远不会是 Link.empty。 注意这里赋值发生在 __init__ 之后，绕过了那句 assert—— 断言只在构造时检查一次，事后改属性它管不着。这也是可变对象的代价。

>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
1
>>> link2.rest.first
2

Link(1, link) 把整条已有链表当作新节点的尾巴，不复制。 所以 link2.rest is link 为真——和 Q2 里 t3.branches[0] is t1 是同一回事。 往后如果改 link.first，link2.rest.first 会跟着变。 可变结构里，「装进去」等于「共享」，不等于「拷贝」。

7. 整份作业回顾

这份 lab 表面上是五道树的题，实际上在反复训练三件事。

一、先决定递归的「签名语义」

动手写第一行之前，先回答：我的函数是返回一个新值，还是就地修改？ 这两类的写法差别很大：

二、树递归的 base case 有两副面孔

Q1 必须显式写 if t.is_leaf(): return t.label， Q2、Q3、Q4 一行 base case 都没有却完全正确。区别在于：

• 如果递归结果是靠 for b in t.branches 累积出来的 （累加到列表、拼字符串、或者纯粹做副作用），叶子的空 branches 会让循环退化成空操作， base case 自动成立，不用写。
• 如果要对分支结果做 max / min / 取第一个 这类需要至少一个元素的运算， 就必须显式挡住叶子，否则 ValueError: max() arg is an empty sequence。

三、可变性带来的两个新问题

用函数式抽象写树时，这两个问题根本不存在；换成类之后，它们每次都要想一遍：

四、额外信息怎么带进递归

Q2 需要「当前深度」，Q5 也需要「当前深度」，但两题的解法完全不同， 这个对比值得单独记住：

五、题目速查