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

2024-03-29 10:26:42 发布

您现在位置:Python中文网/ 问答频道 /正文

我必须获得二叉树中所有根到叶的路径。现在这通常是一项简单的任务,但现在我还必须识别左侧和右侧节点。也就是说,当我进入一个节点的左子树时,该节点应该被记录在路径中为!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 treebinary search tree path list,但我只得到了更多的错误。请帮忙


Tags: path路径righttreedatagetif节点
1条回答
网友
1楼 · 发布于 2024-03-29 10:26:42

问题是,当您将树路径保存到路径时,不会删除树路径的内容

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

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)

相关问题 更多 >