Wie erhalte ich den Pfad von der Wurzel eines Binärbaums zu allen Blättern in Python?
过去多啦不再A梦
过去多啦不再A梦 2017-05-18 10:50:28
0
1
609
'''这是二叉树的定义''' 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)

Das ist mein Code, aber er druckt jedes Mal alle Knoten. Dann entdeckte DEBUG, dass das tmp-Array jedes Mal, wenn es zum rechten Teilbaum zurückkehrt, den Zustand des linken Teilbaums beibehält, bevor es ihn durchquert, was überhaupt nicht der Zustand von der Wurzel zum rechten Teilbaum ist.
Ist das ein Problem mit dem Umfang? Da ich aber keine Lösung finde, bitte ich hier um eine Antwort, danke

过去多啦不再A梦
过去多啦不再A梦

Antworte allen (1)
过去多啦不再A梦

是作用域的问题,你的算法大概没有多少问题,主要是你要知道,给函数传参的时候,尤其是传入可变参数(你这里是列表)的时候,你要做到心中有数。这里你的问题主要集中在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)
    Neueste Downloads
    Mehr>
    Web-Effekte
    Quellcode der Website
    Website-Materialien
    Frontend-Vorlage
    Über uns Haftungsausschluss Sitemap
    Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!