問題描述

’’’這是二叉樹的定義’’’class TreeNode: def __init__(self, val):self.val = valself.left, self.right = None, None’’’這是路徑函數(shù)’’’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)

這是我的代碼，但是每次都是打印全部節(jié)點(diǎn)。然后DEBUG發(fā)現(xiàn)，每次遞歸到右子樹，tmp數(shù)組會(huì)保留之前遍歷完左子樹的狀態(tài)，而根本不是我想的從根到右子樹的狀態(tài)。這是作用域的問題？可我找不到怎么解決，在此請(qǐng)求解答，謝謝

問題解答

是作用域的問題，你的算法大概沒有多少問題，主要是你要知道，給函數(shù)傳參的時(shí)候，尤其是傳入可變參數(shù)（你這里是列表）的時(shí)候，你要做到心中有數(shù)。這里你的問題主要集中在tmp上面，之所以會(huì)保留左子樹的狀態(tài)，是因?yàn)槟阍诒闅v左子樹的時(shí)候，添加了左子樹到tmp中了，然后你又在下一次遞歸調(diào)用中把添加后的列表放到了列表中，如果只有左子樹，是沒問題的，如果有右子樹，就會(huì)出現(xiàn)問題。語言表達(dá)能力有限，我把改過的代碼貼出來給你看看

import copyclass TreeNode: def __init__(self, val):self.val = valself.left, self.right = None, Nonedef dfs(node, result, tmp=list()): if node is None:return tmp.append(node) # 這里需要用拷貝而不是用 = 賦值，也可以遍歷賦值 tmp1 = copy.deepcopy(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) # 遍歷右子樹需要帶上不同的變量，否則左子樹的tmp和右子樹的tmp都指向一塊內(nèi)存 if node.right is not None:dfs(node.right, result, tmp1)if __name__ == ’__main__’: node1 = TreeNode(’a’) node2 = TreeNode(’b’) node3 = TreeNode(’c’) node4 = TreeNode(’d’) node5 = TreeNode(’e’) node6 = TreeNode(’f’) node7 = TreeNode(’g’) node1.left = node2 node1.right = node3 node2.left = node4 node2.right = node5 node4.left = node6 node3.left = node7 r = [] dfs(node1, result=r) print(r)