在逛segmentfault的时候，看到一个比较有意思的算法题：python怎么获得二叉树根到所有叶子的路径？
然后题主贴出了自己的代码，大概就是这样子的
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
def dfs(node, result, tmp):
if node == None:
return
tmp.append(node)
if node.left == None and node.right == None:
result.append([i.val for i in tmp])
return
dfs(node.left, result, tmp)
dfs(node.right, result, tmp)
问题提得还是很规矩，该告知的信息都告知了，所以忍不住想回答一下。
初看这段代码，不知道大家是否能立刻察觉到这段代码有一些很值得注意的地方。嗯，就是他在函数传参的时候使用了列表。在初学Python的时候，无论是书上还是大神的博客上，都告诉我们，不要使用可变参数作为函数参数，否则参数会保持上一次被改变的状态。现在回过头来看看上面给出的代码，tmp和result在每次递归调用后，它们的状态都会被改变。result的改变是我们可以预见并且也是期望的，但是tmp却不好控制。如果我们在遍历左子树的时候把tmp当成参数传到下一次的递归调用中，然后当我们遍历右子树的时候，其添加了左子树的状态还在，所以会出现『tmp数组会保留之前遍历完左子树的状态』这个问题，知道了问题，那么剩下的就是找方法解决这个问题了。
由于左子树和右子树遍历不能互相影响，所以光用一个tmp是不行的，需要一份它的拷贝，注意，这里的拷贝如果只是简单的tmp1 = tmp赋值的话，你会发现效果还是和前面的一样，因为tmp1和tmp指向了同一块地址。对于tmp1和tmp任意一个的修改都会影响对方。正确的做法是使用copy模块的copy或者deepcopy，也就是常说的浅拷贝和深拷贝。两者也是有一些区别的，浅拷贝会把原来的内容都做一份拷贝，如果原来的内容中有可变对象，它会持有该对象的引用，无论是原来的变量或者拷贝的对象对可变对象的改动都会影响到另外一个，而深拷贝不会存在这个问题，它会把所有内容的值都拷贝一份，包括可变对象。比如
>>>a = [1, 2, [3, 4]]
>>>import copy
>>>b = copy.copy(a)
>>>b
[1, 2, [3, 4]]
>>> b[1] = 5
>>>b
[1, 5, [3, 4]] # 修改后的b
>>> a
[1, 2, [3, 4]] # 改变不可变对象，那么原对象不受影响
>>>b[2].append(5)
>>>b
[1, 5, [3, 4, 5]] # 当前b的值
>>>a
[1, 2, [3, 4, 5]] # a 被b的操作影响了,浅拷贝『共享可变对象』
而如果是deepcopy，可以看看同样的操作产生的结果
>>>a = [1, 2, [3, 4]]
>>>b = copy.deepcopy(a)
>>>b
[1, 2, [3, 4]]
>>>b[2].append(5)
>>>b
[1, 2, [3, 4, 5]] # b当前的值
>>>a
[1, 2, [3, 4]] # a当前的值并不会受到影响，深拷贝不会共享可变对象
最后贴上改正过后的代码，『遍历获取二叉树的所有可达路径』
import copy
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
def dfs(node, result, tmp=list()):
if node is None:
return
tmp.append(node)
tmp1 = copy.copy(tmp)
if node.left is None and node.right is None:
result.append([i.val for i in tmp])
return
if node.left is not None:
dfs(node.left, result, tmp)
if node.right is not None:
dfs(node.right, result, tmp1)
网友评论