如何在Python中返回随机二叉树的所有可能路径

Question

我有以下形式的随机二叉树

12

13、14

29、26、89

每个节点有两个子节点，即 (12->(13, 14), 13->(29, 26), 14 ->(26, 89))。这里我需要以 [[12, 13, 29], [ 12, 13, 26], [12, 14, 26], [12, 14, 89]] 的形式返回所有可能的路径。我尝试使用以下代码。我在更新列表时遇到问题。提前致谢。

class Tree:

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __str_(self):
        return '%s' % self.data

def makeList(tree, path =[]):
    if(tree != None):
        path.append(tree.data)
        if tree.left:
            path.append(makeList(tree.left, path))
        if tree.right:
            path.append(makeList(tree.left, path))

    return path

根 = 树（12）

root.left = 树（13）

root.right = 树（14）

root.right.left = 树（26）

root.left.right = 树（26）

root.left.left = 树（29）

root.right.right = 树（86）

x = makeList(root)

Answer 1

我不知道如何使用memoized recursion来解决它。但我仍然发布我的答案，因为它可以部分解决您的问题。

def makeList(tree):
    paths = []
    if not (tree.left or tree.right):
        return [[tree.data]]
    if tree.left:
        paths.extend([[tree.data] + child for child in makeList(tree.left)])
    if tree.right:
        paths.extend([[tree.data] + child for child in makeList(tree.right)])
    return paths