Python (năng suất): tất cả các đường dẫn từ lá này sang gốc khác trên cây

Question

Tôi muốn tạo tất cả các đường dẫn từ mọi lá đến gốc trong cây. Tôi muốn làm điều đó với máy phát điện, để tiết kiệm bộ nhớ (cây có thể lớn). Đây là mã của tôi:

def paths(self, acc=[]): 
    if self.is_leaf(): 
     yield [self.node]+acc 

    for child in self.children: 
     child.paths([self.node]+acc) 

Nhưng nó không hoạt động. Tại sao? Viện dẫn ở gốc, nó đi qua cây từ trên xuống dưới, thu thập các nút trong "acc". "acc" phải được trả về trong mỗi lá ...

is_leaf() là đúng nếu self.children trống.

Answer 1

Mã này chỉ mang lại lá (ngay) con của gốc. Những cái khác được truy cập, chúng sinh ra hàm trên, nhưng hàm trên không làm gì với chúng. Những gì bạn cần là mang lại cho họ từ chức năng thấp hơn đến chức năng phía trên:

def paths(self, acc=[]): 
    if self.is_leaf(): 
     yield [self.node]+acc 

    for child in self.children: 
     for leaf_path in child.paths([self.node]+acc): # these two 
      yield leaf_path       # lines do that 

Điều này nên thực hiện thủ thuật.

Answer 2

Hiện tại, vòng lặp for không yield bất kỳ thứ gì. Thay vào đó, nó sẽ mang lại tất cả các yếu tố được tạo bởi cuộc gọi đệ quy:

for child in self.children: 
    for path in child.paths([self.node]+acc): 
     yield path