使用 python 打印二叉树中的所有路径

Question

所以我有一个非常愚蠢的问题，我似乎无法弄清楚。我只是想打印所有路径以及它们是如何使用先序遍历从二叉树形成的。为此，我将每个值存储在一个数据结构中。我的问题是，为什么在使用 string 与在途中存储每个值时使用 list 时行为会发生变化？

对于具有以下定义的二叉树：

class BinaryTree:
    def __init__(self, value, left_child=None, right_child=None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

left_branch = BinaryTree(5, BinaryTree(3, BinaryTree(7), BinaryTree(10)))
right_branch = BinaryTree(8, None, BinaryTree(4, BinaryTree(6), BinaryTree(9)))
root_tree = BinaryTree(1, left_branch, right_branch)

看起来像这样：

使用字符串存储和打印值时：

def dfs(root, path):
    if root:
        path += str(root.value)
        print(path)
        dfs(root.left_child, path)
        dfs(root.right_child, path)

dfs(root_tree, '')

我得到一个输出：

1
15
153
1537  <-- 1st
15310 <-- 2nd
18
184
1846  <-- 3rd
1849  <-- 4rd

没关系。

但是当我使用列表时：

def dfs(root, path):
    if root:
        path.append(root.value)
        print(path)
        dfs(root.left_child, path)
        dfs(root.right_child, path)

dfs(root_tree, [])

它似乎并没有做同样的事情，因为它只是将所有节点存储在同一路径上：

[1]
[1, 5]
[1, 5, 3]
[1, 5, 3, 7]                 <-- 1st
[1, 5, 3, 7, 10]             <-- ???
[1, 5, 3, 7, 10, 8]
[1, 5, 3, 7, 10, 8, 4]
[1, 5, 3, 7, 10, 8, 4, 6]
[1, 5, 3, 7, 10, 8, 4, 6, 9]

我似乎无法理解为什么会这样。

Answer 1

这是因为字符串是不可变类型，而列表是可变的。

现在，当您在函数中传递字符串（递归）时，每当它被修改时，都会创建一个新的字符串实例，因为无法修改原始字符串。 字符串是不可变的

但是在列表中，对列表所做的修改不会跨函数调用创建新实例。 Python不介意改变原来的列表，因为列表是可以修改的。 列表是可变的。

python这种处理列表的行为，可以说是内存优化，也可以说是OOP的纯粹本质。

要对列表做同样的事情，只需像这样更改代码：

def dfs(root, path):
    if root:
        path.append(root.value)
        print(path)
        dfs(root.left_child, path.copy())
        dfs(root.right_child, path.copy())

dfs(root_tree, [])

copy() 使用原始列表创建一个新的非共享内存列表对象

但是，这样做会使程序消耗比以前更多的内存。

使用 python 打印二叉树中的所有路径

Printing all paths from a binary tree with python

python

recursion

binary-tree