主页 / coding / 问题 / 79354652
Accepted
Hyde Fukui
Asked: 2025-01-14 18:18:55 +0800 CST

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

  • 772

在树形结构数据的类中，我尝试获取从某个节点到根的路径。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']
python-3.x

2 个回答

  1. 您定义了path=[]，这是一个默认参数，并且它只会创建一次，并非每次调用函数时都会创建。

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

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

    def get_forward_path(self, path=None):
    if path is None:
        path = [] 
    
    if not self.parent:
        path.append(self.data)
    • 1
  2. Best Answer

    递归是函数式的传承，因此以函数式风格使用它会产生最佳效果。这意味着要避免诸如变异、变量重新分配和其他副作用之类的事情。

    当你写 时path.append(something)，append函数会改变path变量。与其改变变量，不如使用+which 以非破坏性的方式连接列表 -

    def get_forward_path(self, path=[]):
    next_path = [self.data] + path   # ✅ no mutation!
    if not self.parent:
        return next_path
    else:
        return self.parent.get_forward_path(next_path)

    path=[]遵守这个纪律，使用默认值没有问题。

    增加的好处是，请注意，我们在创建输出列表时添加数据，这意味着我们不必考虑反转最终输出。

    • 1

相关问题