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

Question

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

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] 作为输出。我已经尝试了这里给出的许多建议：print all root to leaf paths in a binary tree and 但我只会收到更多错误。请帮忙

Answer 1

问题是当您将 treepath 保存到 path 时，您并没有删除 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)

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

Obtain all root to leaf paths in binary tree while also identifying directions

python

tree

binary-tree

decision-tree

python-3.x