python - 列出通用(非二元)列表树中叶子的所有路径

Question

我有一棵以这种方式编码的树:

[A, [B, [G, [H], [I]]], 
    [D, [C], [E], [F]]]

这代表以下结构:

        A
       / \
      B   D
     /   /|\
    G   C E F
   / \
  H   I

此外，叶子都包含“end”而不是实际的字母，因此 H、I、C、E、F 实际上都是“end”

另一种查看列表的方式可能更直观。在本例中，缩进代表树级别

[A, 
    [B, 
        [G, 
            [H], 
            [I]
        ]
    ], 
    [D, 
        [C], 
        [E], 
        [F]
    ]
]

我想遍历树并列出所有到达叶子的路径

[A, B, G, H]
[A, B, G, I]
[A, D, C]
[A, D, E]
[A, D, F]

我编写了这个函数，可以遍历树并正确识别叶子，但我不确定如何将路径构建为上面的列表:

def leave_paths(lst, level=0):
    #level is used to keep track how far in the tree we are to
    #perform various functions - removed here for simplicity
    if lst[0] == 'end':
        #This is a leaf!
    for i, l in enumerate(lst[1:]): 
        if type(l) is list:
            leave_paths(l, level + 1)

据我所知，这是正确的，但我不确定如何跟踪路径，以便它们按照我描述的方式格式化。

Answer 1

通过递归，您应该确定您的基本案例，然后如何通过简单的单独步骤在该基本案例的基础上构建更复杂的案例。

基本案例: 叶子是每条路径所独有的，这似乎是一个线索，表明您可以在构建路径时从叶子开始。将包含叶子的列表作为返回值传递回来，这是您的基本情况。在只有一个节点的情况下，您最终只会在单个列表中得到一个值(只有一个路径)。

递归情况:您需要获取递归结果(根据您的示例最多有 2 个分支)，然后将当前节点添加到每个子级结果列表的前面(可能超过2 除非当前节点下方没有分支)。返回前置后的结果。

编辑:既然您如此好意地要求提供一些代码，那么基本上您可以执行以下操作:

def leave_paths(current):
    # Identify leaves by their length
    if len(current) == 1:
        return current
    # Take all branches, get the paths for the branch, and prepend current
    return [[current[0]] + path for branch in current[1:] for path in leave_paths(branch)]

这将为您提供一个“路径”列表的列表。请注意，我们如何通过迭代分支es，然后迭代每个分支的结果path，在每个递归步骤中重新展平>，并将前置结果放入单个结果列表理解中作为我们的返回值。