In week 7, there are more about recursive methods and the Tree class. The contents of lectures are clear and easy to understand. However, for the first time I feel the lab exercise is challenging. Both my lab partner and I struggled to implement the method list_longest_path(node). This method supposes to return a list of the data of a longest path of the node. We started with an if statement that indicates the base case:
if node is None:
return []
Then we also found cases that do not need recursions, which is the Tree only contains one leaf(the length of the path is 1):
elif is_leaf(node):
return [node.data]
So far we were confident and clear. However, what we did not notice is that, besides the case above, there are two more cases that we could implement directly without recursions(the length of the path is 2); and these codes are very important for the recursion to work:
elif node.right is None:
return [node.data, node.left.data]
elif node.left is None:
return [node.data, node.right.data]
With these codes that construct a loop for the recursion to work, we finally successfully implemented list_longest_path(node) method:
else:
left = list_longest_path(node.left)
right = list_longest_path(node.right)
return [node.data] + left if len(left) > len(right) else [node.data] + right
The main problem we encountered was that we always forgot to contain the node.data of the parent tree in the list. We also had a hard time figuring out how to make the program choose the longer path amoung node.left and node.right.
There might be tuns of similar problems that I will encounter in the furture, but the ideas of implementation are the same. Therefore, understanding the essentials of implmenting recursive methods will be extremely helpful for me in my furture programming experience.
No comments:
Post a Comment