使用迭代而不是递归在Python中遍历二叉树

Question

在下面的二叉树中，只有叶子节点保存值，没有内部节点保存值。我使用递归实现了遍历（计算叶子节点保存的值的总和）：

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方法中使用迭代而不是递归？

- Muhammadjon

---

迭代是什么意思？每次迭代都会增加深度级别吗？ - ToTheMax

@ToTheMax 我的意思是使用循环，而不是递归。 - Muhammadjon

Answer 1

您可以使用深度优先搜索算法，它采用 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

- ToTheMax

Answer 2

你甚至可以尝试一些技巧。

import re

treerep = [[3, [5, -1]], [[1, 7], [2, [3, [11, -9]]]]]

p = re.compile('(\[|\]|,)')
treerep = p.sub('', str(treerep))
treerep = [int(i) for i in treerep.split()]

sum(treerep)

易懂))

- Kholdarbekov

---

抱歉，这不是我想要的 :) - Muhammadjon

Answer 3

collections 中的 deque 对象非常适合实现“手动”堆栈，并且可以帮助进行此类遍历。我建议定义一个迭代器方法，使用循环（和 deque）遍历层次结构，然后使用该方法来实现 sum_leaves() 方法。

from collections import deque

def traverse(self,condition=None): # on the Node class
    nodes = deque([self])
    while nodes:
        node = nodes.popleft()
        if not condition or condition(node): yield node
        if node.isLeaf: continue
        if node.left:  nodes.append(node.left)
        if node.right: nodes.append(node.right)

@property
def isLeaf(self): isinstance(self,Leaf)  # on the Node class

def sum_leaves(self): # on the Node class
    return sum(n.val for n in self.traverse(lambda n:n.isLeaf))

def sum_leaves(self): # on the Tree class
    return self.root.sum_leaves()

我相信，如果您不将树结构分为3个不兼容的类别，代码中会有更少的异常。所有节点（包括应该自身作为根的树）都应该能够具有左、右和值属性（至少在签名级别上）。

- Alain T.