打印二进制树(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