获取二叉树中的所有根到叶路径，同时确定方向

Question

我必须获取二叉树中所有根到叶的路径。现在这通常是一项简单的任务，但现在我还必须识别左右节点。也就是说，当我进入节点的左子树时，该节点应记录在路径中为！abc，其中abc是节点名称。当进入右子树时，该节点应按原样记录。所以如果我的树是1（左）2（右）3，那么必须保存的两条路径是！1-

def get_tree_path(root, paths, treepath):
    if not root:
        return
    if not root.left and not root.right:
        treepath.append(root.data)
        paths.append(treepath)
        
    if root.left:
        treepath.append('!'+root.data[0])
        get_tree_path(root.left, paths, treepath)

    if root.right:
        treepath.append(root.data[0])
        get_tree_path(root.right, paths, treepath)

这确实获得了路径。但左右子树路径都连接在一起。也就是说，对于上面给出的示例，我得到[1，3，1，2]作为输出。我尝试了这里给出的许多建议：在二叉树和二叉搜索树路径列表中打印所有根到叶的路径，但我只会得到更多的错误。请帮忙。

Answer 1

问题是，当您将treepath保存到路径时，您不会删除treepath的内容。

为此，您需要为每个递归调用创建一个新列表：

if root.left:
    treepath_left = list(treepath)
    treepath_left.append('!'+root.data[0])
    get_tree_path(root.left, paths, treepath_left)

if root.right:
    treepath_right = list(treepath)
    treepath_right.append(root.data[0])
    get_tree_path(root.right, paths, treepath_right)