# 返回二叉樹中的值列表

def __init__(self, item, left=None, right=None):
"""(BTNode, object, BTNode, BTNode) -> NoneType
Initialize this node to store item and have children left and right,
as well as depth 0.
"""
self.item = item
self.left = left
self.right = right
self.depth = 0  # the depth of this node in a tree

def number(self: 'BTNode') -> list:
lst = []

if self.right is None and self.left is None:
lst.append(self.item)
else:
lst.append(self.item)
if self.left:
left = self.left.number()
lst.extend(left)
if self.right:
right = self.right.number()
lst.extend(right)
return lst


## 最佳答案

There is no docstring for the number method.

There are no test cases. This kind of code would be an ideal opportunity to write some doctests.

The depth property is always 0. This seems useless.

The method name number is misleading. (It does not return a number.) I would call it something like flattenedpreorder because it flattens the tree into a list using pre-order traversal.

The variable name lst is misspelt. Better to call it something like result.

This code: if self.right is None and self.left is None: lst.append(self.item) else: lst.append(self.item)

can be replaced with: lst.append(self.item)

since it doesn't matter whether the condition is true or false.

There's quite a lot of copying going on in the traversal of the tree: each time you call a.extend(b), Python has to copy out the list b. This copying causes the traversal of a tree with n nodes to take O(n2) time instead of O(n). See below for a way to avoid this copying.

You use recursion to visit the child nodes, which means that traversing a very deep tree will exceed Python's maximum recursion depth:

n = None for i in range(1000): n = BTNode(i, n) ... n.number() Traceback (most recent call last): File "", line 1, in File "cr33662.py", line 22, in number left = self.left.number() [... many lines omitted ...] RuntimeError: maximum recursion depth exceeded

The way to avoid this is to maintain your own stack, like this: def flattenedpreorder(self: 'BTNode') -> list: """Return a list of items in the tree rooted at this node, using pre-order traversal.

    >>> tree = BTNode(1, BTNode(2, None, BTNode(3)), BTNode(4))
>>> tree.flattened_pre_order()
[1, 2, 3, 4]
>>> node = BTNode(9999)
>>> for i in range(9998, -1, -1): node = BTNode(i, node)
>>> node.flattened_pre_order() == list(range(10000))
True

"""
result = []
stack = [self]
node = None
while stack:
if node is None:
node = stack.pop()
if node is not None:
result.append(node.item)
stack.append(node.right)
node = node.left
return result