在逛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)

問題提得還是很規(guī)矩，該告知的信息都告知了，所以忍不住想回答一下。

初看這段代碼，不知道大家是否能立刻察覺到這段代碼有一些很值得注意的地方。嗯，就是他在函數(shù)傳參的時候使用了列表。在初學(xué)Python的時候，無論是書上還是大神的博客上，都告訴我們，不要使用可變參數(shù)作為函數(shù)參數(shù)，否則參數(shù)會保持上一次被改變的狀態(tài)?，F(xiàn)在回過頭來看看上面給出的代碼，tmp和result在每次遞歸調(diào)用后，它們的狀態(tài)都會被改變。result的改變是我們可以預(yù)見并且也是期望的，但是tmp卻不好控制。如果我們在遍歷左子樹的時候把tmp當(dāng)成參數(shù)傳到下一次的遞歸調(diào)用中，然后當(dāng)我們遍歷右子樹的時候，其添加了左子樹的狀態(tài)還在，所以會出現(xiàn)『tmp數(shù)組會保留之前遍歷完左子樹的狀態(tài)』這個問題，知道了問題，那么剩下的就是找方法解決這個問題了。

由于左子樹和右子樹遍歷不能互相影響，所以光用一個tmp是不行的，需要一份它的拷貝，注意，這里的拷貝如果只是簡單的tmp1 = tmp賦值的話，你會發(fā)現(xiàn)效果還是和前面的一樣，因為tmp1和tmp指向了同一塊地址。對于tmp1和tmp任意一個的修改都會影響對方。正確的做法是使用copy模塊的copy或者deepcopy，也就是常說的淺拷貝和深拷貝。兩者也是有一些區(qū)別的，淺拷貝會把原來的內(nèi)容都做一份拷貝，如果原來的內(nèi)容中有可變對象，它會持有該對象的引用，無論是原來的變量或者拷貝的對象對可變對象的改動都會影響到另外一個，而深拷貝不會存在這個問題，它會把所有內(nèi)容的值都拷貝一份，包括可變對象。比如

>>>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]] # 當(dāng)前b的值
>>>a
[1, 2, [3, 4, 5]]  # a 被b的操作影響了,淺拷貝『共享可變對象』

而如果是deepcopy，可以看看同樣的操作產(chǎn)生的結(jié)果

>>>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當(dāng)前的值
>>>a
[1, 2, [3, 4]]    # a當(dāng)前的值并不會受到影響，深拷貝不會共享可變對象

最后貼上改正過后的代碼，『遍歷獲取二叉樹的所有可達(dá)路徑』

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)