使用查找二叉樹葉子和節點

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）。

也就是說，此功能將不返回所有葉子的總和（即它不會遍歷多層次樹的情況下，整個樹）。