打印二叉樹（DFS）的所有路徑

Question

我試圖打印二叉樹的所有路徑（根到葉路徑），但無濟於事。

我的策略是使用遞歸，其基本情況爲either tree is None or tree node is leaf return否則，遍歷樹的左側和右側。

但我找不到保留左右樹的方法。

def pathSum(self, root, target, result): 

    if not root: 
     return [] 

    if not root.left and not root.right: 
     return [root.val] 

    for i in [root.left, root.right]: 
     path = [root.val] + self.pathSum(i, target, result) 
     print("path", path) 
     return path 

Answer 1

的想法在每個節點訪問正在建設的路徑（列表），如果當前節點是葉，增加電流路徑，並打印出來，如果沒有，只是增加電流擴展的路徑：

def pathSum(self, path): 

    if not self.left and not self.right: 
     print(path + [self.val]) 
     return 

    self.left.pathSum(path + [self.val]) 
    self.right.pathSum(path + [self.val]) 


root.pathSum([]) 

更新：如果你想保留的所有路徑：

def pathSum(self, current_path, all_paths): 

    if not self.left and not self.right: 
     print('Path found: ' + str(current_path + [self.val])) 
     all_paths.append(current_path + [self.val]) 
     return 

    self.left.pathSum(current_path + [self.val], all_paths) 
    self.right.pathSum(current_path + [self.val], all_paths) 

all_paths = [] 

root.pathSum([], all_paths) 

print('All paths: ' + str(all_paths)) 

Answer 2

通過一些迭代，我發現下面的解決方案工作。但我不確定是否有更有效的方法來查找所有葉根路徑。

這一解決方案背後的想法是前序遍歷

def allPaths(self, root, path, all_path): 
    if not root.left and not root.right: 
     path.append(root.val) 
     all_path.append(path[:]) 
     return 

    if root: 
     path.append(root.val) 
     self.allPaths(root.left, path, all_path) 
     path.pop(-1) 
     self.allPaths(root.right, path, all_path) 
     path.pop(-1) 
    return all_path