Python3树形结构中节点到根路径递归函数异常问题

我在树形结构的类里尝试获取指定节点到根节点的路径，下面的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

调用get_forward_path()的异常结果 #

第一次调用：

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']

原因分析 #

这是Python默认参数的经典陷阱：默认参数在函数定义阶段就会被初始化一次，而不是每次调用时重新创建。你把path=[]作为默认参数，这个列表对象会在get_forward_path方法第一次被定义时就生成，之后每次调用如果不传path参数，都会复用同一个列表对象。每次调用方法时往这个列表里追加元素，自然会导致列表越来越长，哪怕调用的是不同节点。

修复方案 #

方案1：修改默认参数为None，内部创建新列表 #

把默认参数改成None，在方法内部判断后创建新的空列表，这样每次调用都会使用新列表，避免复用：

def get_forward_path(self, path=None):
    if path is None:
        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]

方案2：优化逻辑，避免递归传递列表 #

可以直接从当前节点向上遍历到根节点，收集路径数据，逻辑更简洁，还能避免递归深度过大的问题：

def get_forward_path(self):
    path = []
    current = self
    while current:
        path.append(current.data)
        current = current.parent
    return path[::-1]

这个版本不需要依赖默认参数，直接从当前节点开始循环向上找父节点，把数据加入列表，最后反转得到从根到当前节点的路径，完全避开了默认参数的陷阱，代码也更易读。

内容的提问来源于stack exchange，提问作者Hyde Fukui