一千萬個為什麽

搜索

返回二叉樹中的值列表

我想返回二叉樹中的值列表。是否有更短更有效的方法來編寫數字方法? class BTNode(object): """A node in a binary tree."""

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

轉載註明原文: 返回二叉樹中的值列表