打印二叉树（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