在树结构数据中查找根路径（Python3中的递归函数）

Question

在树结构数据的类中，我试图获取从某个节点到根的路径。 下面的

get_forward_path()

方法在第一次运行时有效，但每次运行该方法时，其输出列表都会永远增长。即使我将该方法应用于不同的节点，它也会不断增长。 即使在调用该方法时将

path

参数重置为其默认值（空白列表），为什么还会发生这种情况？

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None
        
    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self):
        spaces = ' ' * self.get_level() * 3
        prefix = spaces + "|__" if self.parent else ""
        print(prefix + self.data)
        if self.children:
            for child in self.children:
                child.print_tree()
    
    def get_forward_path(self,path=[]):
        if not self.parent:
            path.append(self.data)
        else:
            path.append(self.data)
            p = self.parent
            p.get_forward_path(path)
        return path[::-1]

    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level += 1
            p = p.parent

        return level

root = TreeNode("Electronics")

laptop   = TreeNode("Laptop")
Mac      = TreeNode("Mac")
Surface  = TreeNode("Surface")
ThinkPad = TreeNode("ThinkPad")
laptop.add_child(Mac)
laptop.add_child(Surface)
laptop.add_child(ThinkPad)

cellphone    = TreeNode("Cell Phone")
iPhone       = TreeNode("iPhone")
Google_Pixel = TreeNode("Google Pixel")
Vivo         = TreeNode("Vivo")
cellphone.add_child(iPhone)
cellphone.add_child(Google_Pixel)
cellphone.add_child(Vivo)

tv      = TreeNode("TV")
Samsung = TreeNode("Samsung")
LG      = TreeNode("LG")
tv.add_child(Samsung)
tv.add_child(LG)

root.add_child(laptop)
root.add_child(cellphone)
root.add_child(tv)

root.print_tree()

Electronics
   |__Laptop
      |__Mac
      |__Surface
      |__ThinkPad
   |__Cell Phone
      |__iPhone
      |__Google Pixel
      |__Vivo
   |__TV
      |__Samsung
      |__LG

Samsung.get_forward_path()

['Electronics', 'TV', 'Samsung']

Samsung.get_forward_path()

['Electronics', 'TV', 'Samsung', 'Electronics', 'TV', 'Samsung']

iPhone.get_forward_path()

['Electronics',
 'Cell Phone',
 'iPhone',
 'Electronics',
 'TV',
 'Samsung',
 'Electronics',
 'TV',
 'Samsung']

Answer 1

您定义了

path=[]

，这是默认参数并且已创建一次 不是每次调用该函数时。

因此它是在第一次调用 get_forward_path 函数时创建的，并且 然后代码继续使用相同的参数（append）。

解决办法很简单： 在函数 def 中使用 path = None 然后检查路径是否为 None，然后创建空列表

def get_forward_path(self, path=None):
    if path is None:
        path = [] 
    
    if not self.parent:
        path.append(self.data)