使用查找二叉树叶子和节点

Question

我希望能够通过使用节点的递归找到一个二叉树的所有叶子的总和到目前为止我有：

class BTNode: 
    """A node in a binary tree.""" 

    def __init__(self: 'BTNode', item: object, 
       left: 'BTNode' =None, right: 'BTNode' =None) -> None: 
    """Initialize this node. 
    """ 
    self.item, self.left, self.right = item, left, right 

    def __repr__(self): 
    return 'BTNode({}, {}, {})'.format(repr(self.item), 
        repr(self.left), repr(self.right)) 

    def is_leaf(self: 'BTNode') -> bool: 
    return not self.left and not self.right 


def tree_sum(t: BTNode) -> int: 
    '''Return the sum of the leaves in t. 

    >>> t = BTNode(None, BTNode(8), BTNode(9)) 
    >>> tree_sum(t) 
    17 
    ''' 
    sm = 0 
    t1 = t.left.item 
    t2 = t.right.item 
    if not t.left or not t.right: 
    return 0 
    if t.left.is_leaf() and t.right.is_leaf(): 
    sm = t1 + t2 + tree_sum(t.left) + tree_sum(t.right) 
    return sm 

的函数tree_sum（t）我没有工作，我正在努力寻找一种可行的方法。我做错了什么？

Answer 1

您错过了一小段代码。

由于t.left和t.right将None如果t是叶，线条t1 = t.left.item和t2 = t.right.item将引发AttributeError。

你需要考虑到这一点：

t1 = t.left.item if t.left else None 
t2 = t.right.item if t.right else None 

然后

t = BTNode(None, BTNode(8), BTNode(9)) 
print(tree_sum(t)) 

产生正确的结果（17）。

也就是说，此功能将不返回所有叶子的总和（即它不会遍历多层次树的情况下，整个树）。