В следующем двоичном дереве остаются только значения хранения, никакие внутренние узлы не содержат значения. Я реализовал обход (чтобы вычислить сумму значений, которые остались) с помощью рекурсии :
class Node:
def new(rep):
if type(rep) is list:
left = Node.new(rep[0])
right = Node.new(rep[1])
return Internal(left, right)
else:
return Leaf(rep)
class Leaf(Node):
def __init__(self, val):
self.val = val
def sum_leaves(self, sum):
return sum + self.val
class Internal(Node):
def __init__(self, left, right):
self.left = left
self.right = right
def sum_leaves(self, sum):
return self.right.sum_leaves(self.left.sum_leaves(sum))
class Tree:
def __init__(self, rep):
self.root = Node.new(rep)
# Traverse the tree and return the sum of all leaves
def sum_leaves(self):
return self.root.sum_leaves(0)
treerep = [[3, [5, -1]], [[1, 7], [2, [3, [11, -9]]]]]
tree = Tree(treerep)
print(tree.sum_leaves())
В этом случае вывод:
22
Как я могу использовать итерацию вместо рекурсии для sum_leaves
метода?