打印二叉树（DFS）的所有路径

Question

我试图打印二叉树的所有路径（根到叶的路径），但没有效果。

我的策略是使用递归，基本情况是树为None或树节点为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 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

Answer 2

想法是在每次节点访问时构建路径（列表），如果当前节点是一片叶子，则将当前添加到路径并打印，如果不是，则只需添加当前以扩展路径：

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))