python怎么获得二叉树根到所有叶子的路径?
本文介绍了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)
这是我的代码,但是每次都是打印全部节点。然后DEBUG发现,每次递归到右子树,tmp数组会保留之前遍历完左子树的状态,而根本不是我想的从根到右子树的状态。
这是作用域的问题?可我找不到怎么解决,在此请求解答,谢谢
解决方案
是作用域的问题,你的算法大概没有多少问题,主要是你要知道,给函数传参的时候,尤其是传入可变参数(你这里是列表)的时候,你要做到心中有数。这里你的问题主要集中在tmp上面,之所以会保留左子树的状态,是因为你在遍历左子树的时候,添加了左子树到tmp中了,然后你又在下一次递归调用中把添加后的列表放到了列表中,如果只有左子树,是没问题的,如果有右子树,就会出现问题。语言表达能力有限,我把改过的代码贴出来给你看看
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.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)
这篇关于python怎么获得二叉树根到所有叶子的路径?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文