CS_106A_lab_09-526互联

重点：：

观察到：在带入函数之后，没有任何返回值，是直接对参数本身进行作用。遇到这种情况就必须在基线条件下多加一个【return】语句

why?

其实就是人为两种情况，第一种就是t是节点，此时只需要将节点平方就可以了。第二种情况就是有分支，首先呢就将root平方，再将分支进行处理。

 1 def label_squarer(t):
 2     """Mutates a Tree t by squaring all its elements.
 3 
 4     >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
 5     >>> label_squarer(t)
 6     >>> t
 7     Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
 8     """
 9     "*** YOUR CODE HERE ***"
10     if t.is_leaf():
11         t.label**=2
12         return #very important
13     else:
14         t.label=t.label**2
15         for branch in t.branches:
16             label_squarer(branch)

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)])
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return t.label
    for branch in t.branches:
        cumulative_mul(branch)
    cumu_ml=t.label
    for b in t.branhces:
        cumu_ml*=b.label
    t.label=cumu_ml

 1 def has_cycle(link):
 2     """Return whether link contains a cycle.
 3 
 4     >>> s = Link(1, Link(2, Link(3)))
 5     >>> s.rest.rest.rest = s
 6     >>> has_cycle(s)
 7     True
 8     >>> t = Link(1, Link(2, Link(3)))
 9     >>> has_cycle(t)
10     False
11     >>> u = Link(2, Link(2, Link(2)))
12     >>> has_cycle(u)
13     False
14     """
15     "*** YOUR CODE HERE ***"
16     p = link
17     visit_set = set()
18     while p != Link.empty:
19         if p in visit_set:
20             return True
21         else:
22             visit_set.add(p)
23         p = p.rest
24     return False

这段代码定义了一个名为has_cycle的函数，它接受一个链表link作为参数，并判断该链表是否存在环，即是否存在一个节点可以通过遍历链表到达之前已经访问过的节点。

函数内部首先定义了一个指针p，指向链表的第一个节点。然后创建了一个空的集合visit_set，用于存储已经访问过的节点。接下来使用while循环遍历链表，如果当前节点p已经存在于visit_set中，则说明存在环，返回True；否则，将当前节点p加入visit_set中，并将p指向下一个节点，继续遍历。如果遍历完整个链表仍然没有发现环，则返回False。

该函数通过用集合visit_set存储已经访问过的节点，来判断是否存在环，时间复杂度为O(n)，其中n是链表的长度。

problem 7:

题目描述：

答案：

 1 def reverse_other(t):
 2     """Mutates the tree such that nodes on every other (odd-depth) level
 3     have the labels of their branches all reversed.
 4 
 5     >>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
 6     >>> reverse_other(t)
 7     >>> t
 8     Tree(1, [Tree(4), Tree(3), Tree(2)])
 9     >>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
10     >>> reverse_other(t)
11     >>> t
12     Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
13     """
14     "*** YOUR CODE HERE ***"
15     if t.is_leaf():
16         return 
17     label_list=[]
18     for b in t.branches:
19         label_list.append(b.label)
20     for b, new_label in zip(t.branches,reversed(label_list)):
21         b.label=new_label
22         for bb in b.branhces:
23             reverse_other(bb)