递归DFS打印一个嵌套列表

Question

我正在尝试使用Python打印嵌套列表，以使我们可以拥有多个副本。

我的问题是：如何用x [0]作为父母在DFS中正确打印此此内容，以及x [1：]作为孩子？

例如，我有此输入，

['1', ['2', ['3', ['4', ['5', ['6', ['7']], ['8', ['9']]]]]]]

并且可以在此结构中进行可视化以可视化：

['1', 
    ['2', 
        ['3', 
            ['4', 
                ['5', 
                    ['6', 
                        ['7']
                    ], 
                    ['8', 
                        ['9']
                    ]
                ]
            ]
        ]
    ]
]

我试图递归印刷，并希望其结果看起来像这样，并且整个路径都打印出来。

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9

但实际上最终在

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
5 -> 8 -> 9

这里得到这个是我的代码片段

def __print(chains: List):
    """
    Assuming the input list where index 0 is the source, and index 1 is its
    children paths.
    """

    if (len(chains) == 0):
        return
    elif (len(chains) == 1):
        # reaching the end
        print("{0}".format(chains[0]))
        return
    else:
        # everything after index 0 is considered children
        children = chains[1:]

        # has children
        for child in children:
            print("{0} -> ".format(chains[0]), end='')
            __print(child)

Answer 1

从理论上讲，您的方法看起来很棒，因为您不需要保持额外的状态。但是没有保持状态的问题。假设您在父节点。您无法知道您应该打印该节点的值多少次，因为您必须向下穿过树，以找出最终是根的叶子节点。缺乏新系列使事情变得更加复杂。

因此，我看不到将路径走到孩子打电话的明显方法。当您达到终端节点时，只需打印将您带到这里的路径即可。否则，将电流节点推到路径上，然后将其传递到递归调用中，然后在探索所有孩子后将其弹出。

我不喜欢在功能中打印。这禁止呼叫者对结果有用。最好返回发电机，让呼叫者按照他们的意愿进行操作。

作为优化，您可以在整个过程中使用一个列表，只有在yarts路径的时候复制。

def find_paths(chains, path=None):
    if path is None:
        path = []

    if not chains:
        return

    path.append(chains[0])

    if len(chains) == 1:
        yield tuple(path)
    else:
        for child in chains[1:]:
            yield from find_paths(child, path)

    path.pop()


if __name__ == "__main__":
    tree = ["1", ["2", ["3", ["4", ["5", ["6", ["7"]], ["8", ["9"]]]]]]]

    for path in find_paths(tree):
        print(" -> ".join(path))

这里的额外空间成本是o（树深）。

另一件事：混合型数据结构很难使用。 变得很容易处理

{
    "value": "1",
    "children": [
        {
            "value": "2",
            "children": [...],
        },
    ],
}

在以下典型的树格中，使用词典将节点有效载荷与孩子分开：这使得找到孩子 。无需切片，这是浪费时间和空间，或者必须做type（）/isInstance（）调用以找出什么（在您的情况下，第一个元素是字符串，其余的是列表，避免了类型检查，但是它接近讨厌的领域...）。