在下面的二叉树中,只有叶子保持值,没有内部节点保持值。我使用递归实现了遍历(计算保留值的总和):
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
如何使用 iteration 而不是 sum_leaves
方法的递归?
最佳答案
您可以使用使用 while 循环的深度优先搜索:
class Tree:
def __init__(self, rep):
self.root = Node.new(rep)
def sum_dfs(self):
sum = 0
stack = [self.root]
while len(stack):
node = stack.pop()
if isinstance(node, Internal):
stack.append(node.left)
stack.append(node.right)
elif isinstance(node, Leaf):
sum += node.val
return sum
关于python - 在 Python 中使用迭代而不是递归遍历二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61069188/