python怎么获得二叉树根到所有叶子的路径？

问题描述

’’’这是二叉树的定义’’’class TreeNode: def __init__(self, val):self.val = valself.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)

这是我的代码，但是每次都是打印全部节点。然后DEBUG发现，每次递归到右子树，tmp数组会保留之前遍历完左子树的状态，而根本不是我想的从根到右子树的状态。这是作用域的问题？可我找不到怎么解决，在此请求解答，谢谢

问题解答

是作用域的问题，你的算法大概没有多少问题，主要是你要知道，给函数传参的时候，尤其是传入可变参数（你这里是列表）的时候，你要做到心中有数。这里你的问题主要集中在tmp上面，之所以会保留左子树的状态，是因为你在遍历左子树的时候，添加了左子树到tmp中了，然后你又在下一次递归调用中把添加后的列表放到了列表中，如果只有左子树，是没问题的，如果有右子树，就会出现问题。语言表达能力有限，我把改过的代码贴出来给你看看

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都指向一块内存 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)