题目：
def is_bst(t): """Returns True if the Tree t has the structure of a valid BST. >>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t1) True >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)]) >>> is_bst(t2) False >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])]) >>> is_bst(t3) False >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])]) >>> is_bst(t4) True >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])]) >>> is_bst(t5) True >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])]) >>> is_bst(t6) True >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)]) >>> is_bst(t7) False """ "*** YOUR CODE HERE ***"
答案：
1 def is_bst(t): 2 """Returns True if the Tree t has the structure of a valid BST. 3 4 >>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])]) 5 >>> is_bst(t1) 6 True 7 >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)]) 8 >>> is_bst(t2) 9 False 10 >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])]) 11 >>> is_bst(t3) 12 False 13 >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])]) 14 >>> is_bst(t4) 15 True 16 >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])]) 17 >>> is_bst(t5) 18 True 19 >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])]) 20 >>> is_bst(t6) 21 True 22 >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)]) 23 >>> is_bst(t7) 24 False 25 """ 26 "*** YOUR CODE HERE ***" 27 # 如何判断是否只有一个children branches ？ len(branches)==1 28 # 大于或者小于子节点都是可以的 29 #所有在右侧的节点都必须大于上一个节点，所有在左侧的节点都必须小于上一个节点。 30 #而且所有在右侧的节点，如果只有一个节点的话，也必须大于最开始的节点 31 #一个节点是很特殊的情况，他可以大于或者小于上一个节点，但是他如果是属于右侧的节点，就必须大于 32 #对于左边右侧的节点，必须大于上一个节点，但是又必须小于上——上个节点，即有两个限制条件 33 #对于右边，左侧的节点，必须小于上一个节点，但是又必须要大于上-上一个节点，也有两个限制条件 34 # 1. at most 2 rbanches 35 # 2. all[is_bst(b) for b in t. branches]==True 36 # 3. bst_max(left)<=t.label 37 # 4. bst_min(right)>t.label 38 # what I learn : write down the demand 39 def bst_min(t): 40 if t.is_leaf(): 41 return t.label 42 elif len(t.branches) == 1: 43 if t.label > t.branches[0].label: 44 return bst_min(t.branches[0]) 45 else: 46 return t.label 47 else: 48 return bst_min(t.branches[0]) 49 50 def bst_max(t): 51 if t.is_leaf(): 52 return t.label 53 elif len(t.branches) == 1: 54 if t.label < t.branches[0].label: 55 return bst_max(t.branches[0]) 56 else: 57 return t.label 58 else: 59 return bst_max(t.branches[1]) 60 61 if t.is_leaf(): 62 return True 63 64 if len(t.branches) == 1: 65 if t.label > t.branches[0].label: 66 return is_bst(t.branches[0]) and t.label >= bst_max(t.branches[0]) 67 else: 68 return is_bst(t.branches[0]) and t.label < bst_min(t.branches[0]) 69 elif len(t.branches) == 2: 70 le,ri=t.branches 71 return is_bst(le) and is_bst(ri) and (bst_max(le) <= t.label <bst_min(ri) ) 72 else: 73 return False
要抽象一点，不要太具象。
题目：
Define a generator function path_yielder which takes in a Tree t, a value value, and returns a generator object which yields each path from the root of t to a node that has label value.
t is implemented with a class, not as the function-based ADT.
Each path should be represented as a list of the labels along that path in the tree. You may yield the paths in any order.
We have provided a (partial) skeleton for you. You do not need to use this skeleton, but if your implementation diverges significantly from it, you might want to think about how you can get it to fit the skeleton.
def path_yielder(t, value): """Yields all possible paths from the root of t to a node with the label value as a list. >>> t1 = Tree(1, [Tree(2, [Tree(3), Tree(4, [Tree(6)]), Tree(5)]), Tree(5)]) >>> print(t1) 1 2 3 4 6 5 5 >>> next(path_yielder(t1, 6)) [1, 2, 4, 6] >>> path_to_5 = path_yielder(t1, 5) >>> sorted(list(path_to_5)) [[1, 2, 5], [1, 5]] >>> t2 = Tree(0, [Tree(2, [t1])]) >>> print(t2) 0 2 1 2 3 4 6 5 5 >>> path_to_2 = path_yielder(t2, 2) >>> sorted(list(path_to_2)) [[0, 2], [0, 2, 1, 2]] """ "*** YOUR CODE HERE ***" for _______________ in _________________: for _______________ in _________________: "*** YOUR CODE HERE ***"
answer
def path_yielder(t, value): """Yields all possible paths from the root of t to a node with the label value as a list. >>> t1 = Tree(1, [Tree(2, [Tree(3), Tree(4, [Tree(6)]), Tree(5)]), Tree(5)]) >>> print(t1) 1 2 3 4 6 5 5 >>> next(path_yielder(t1, 6)) [1, 2, 4, 6] >>> path_to_5 = path_yielder(t1, 5) >>> sorted(list(path_to_5)) [[1, 2, 5], [1, 5]] >>> t2 = Tree(0, [Tree(2, [t1])]) >>> print(t2) 0 2 1 2 3 4 6 5 5 >>> path_to_2 = path_yielder(t2, 2) >>> sorted(list(path_to_2)) [[0, 2], [0, 2, 1, 2]] """ "*** YOUR CODE HERE ***" if t.label==value: yield [t.label] for branch in t.branches: for yid in path_yielder(branch,value): yield [t.label]+yid
反思：
还是自己递归没有学好，递归就是先确定极限条件，对于树尤其简单——就是到了label的时候会怎么样，确定下来就可以了。然后就完全、充分的信任它，回到第二层，就是已经后面都递归好了，应该怎么弄。
具体到这一题：
最开始就是确立了那个基线条件：如果t.label == value 的时候会怎么样，然后就不考虑最底层的情况了，直接就是处理最后每个branch产生的list（因为每个branch可能会产生多个list），再最后拼接上root node就行了。
题目：
Implement a function remove_all that takes a Link, and a value, and remove any linked list node containing that value. You can assume the list already has at least one node containing value and the first element is never removed. Notice that you are not returning anything, so you should mutate the list.
1 def remove_all(link, value): 2 """Remove all the nodes containing value in link. Assume that the 3 first element is never removed. 4 5 >>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3))))))) 6 >>> print(l1) 7 <0 2 2 3 1 2 3> 8 >>> remove_all(l1, 2) 9 >>> print(l1) 10 <0 3 1 3> 11 >>> remove_all(l1, 3) 12 >>> print(l1) 13 <0 1> 14 >>> remove_all(l1, 3) 15 >>> print(l1) 16 <0 1> 17 """ 18 "*** YOUR CODE HERE ***" 19 if link.rest == Link.empty: 20 return 21 22 while link.rest.first == value: 23 link.rest = link.rest.rest 24 if link.rest == Link.empty:# important 25 return 26 27 remove_all(link.rest, value)
第二十四行尤其重要，如果不加这个条件就会出错，为什么？？
因为在语句 remove_all(l1, 3) 的时候，运行到 【1】时，调用link.rest 会将尾部的【3】删除，此时就只有一个元素了，rest=empty，然后进入下一轮循环，判断 link.rest.first == value ，此时就会变成empty.first,但是empty是元祖，没有first这个属性。就会出现错误。以后要注意。