python - 返回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, [])
 

标签： pythonrecursionbinary-search-tree

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