不同行为递归二叉树输出列表 v. 字符串

Question

我正在使用 python.

通过二叉树学习递归

我不明白这两个函数输出的差异。在第一个中，我将遍历编码为 return 一个列表，在第二个中是一个字符串。

对于列表：

class Node:
    def __init__(self, value):
        self.value = value 
        self.left = None 
        self.right = None 

class Tree:
    def __init__(self):
        self.root = None

    def inorder(self, data, traversal=[]):        
        if data:
            self.inorder(data.left, traversal)
            traversal.append(str(data.value))
            self.inorder(data.right, traversal)

        return traversal
"""
       1
      / \
     2   3
    / \   
   4   5
"""
thing = Tree()
thing.root = Node(1)
thing.root.left = Node(2)
thing.root.right = Node(3)
thing.root.left.left = Node(4)
thing.root.left.right = Node(5)

print(thing.inorder(thing.root))

['4', '2', '5', '1', '3']

但是，如果我将 inorder 函数修改为 return 一个字符串：

    def inorder(self, data, traversal=""):        
        if data:
            self.inorder(data.left, traversal)
            traversal += str(data.value)
            self.inorder(data.right, traversal)

        return traversal

'1'

只有当我将递归调用的输出分配给遍历时它才有效，如下所示：

    def inorder(self, data, traversal=""):        
        if data:
            traversal = self.inorder(data.left, traversal)
            traversal += str(data.value)
            traversal = self.inorder(data.right, traversal)

        return traversal

'42513'

我不明白为什么我追加到列表而不是连接字符串时行为会有所不同。有人可以给我解释一下吗？

Answer 1

python 中的字符串是不可变的。您的遍历累加器依赖于突变来工作。您可以修改它以实际使用 return 值，而不是依赖于改变您的“遍历”数据结构。

if data:
    t1 = self.inorder(data.left, "")
    t2 = data.value
    t3 = self.inorder(data.right, "")
    traversal = t1 + t2 + t3

您可以（可能）对列表使用相同的技术。到那时，您将不再需要在递归调用中传递累加器。

不同行为递归二叉树输出列表 v. 字符串

Different behavior recursing binary tree to output list v. string

python

algorithm

binary-tree

binary-search-tree