返回BST python中所有路径的列表

Question

假设我有一个二叉树，从根到叶的路径是3-1-3，3-4-5，3-4-1……我该如何返回所有不同路径的列表呢？到目前为止，这就是我所知道的，但它所做的就是返回[3，1，3，4，1，5，3，1，3，4，1，5，3，1，3，4，1，5]，这是树中所有节点的三个列表，而不是每个路径的单独列表。

self.res = []
def helper(root, temp):
   if not root:
      return
   temp.append(root.val)
   if not root.left and not root.right:
      self.res.append(temp)
      return
   helper(root.left, temp)
   helper(root.right, temp)
helper(root, [])

Answer 1

您不能像这样附加到temp，您需要为左分支和右分支递归调用创建当前temp的不同副本。

下面是递归DFS方法的一个略微修改的版本，通过这样做，它应该可以按您的需要工作：

class BinaryTreePaths:
    def __init__(self):
        self.res = []
    
    def get_binary_tree_paths(self, root):
        if not root:
            return []
        self.helper(root, [])
        return self.res
    
    def helper(self, node, temp):
        if not node.left and not node.right:
            self.res.append(temp + [node.val])
        if node.left:
            self.helper(node.left, temp + [node.val])
        if node.right:
            self.helper(node.right, temp + [node.val])