python之在二叉树中查找所有根到叶的路径(在 Python 中)

我在 Python 中有一些代码应该以列表的形式返回二叉树中所有根到叶的路径(例如 ["1->2->5", "1->3"] ).原题来自leetcode。

我需要帮助找出我的代码和/或替代解决方案(最好是 Python)的问题。对于我上面给出的示例，我的代码返回 null 而它实际上应该打印我给出的列表。当您第一次看到这个问题时，我也很感激您如何解决这个问题。

这是我的代码:

    def binaryTreePaths(self, root): 
        list1 = [] 
        if (root == None):  
            return [] 
        if (root.left == None and root.right == None): 
            return list1.append(str(root.val) + "->")  
        if (root.left != None): 
            list1.append(self.binaryTreePaths(root.left))  
        if (root.right != None): 
            list1.append(self.binaryTreePaths(root.right)) 

请您参考如下方法:

• 缺少返回声明
• 较低级别的递归返回列表，而不是单个值(即 += 与 .append())
• 较低级别递归调用返回的列表中的值应以“root->”为前缀

总计:

def binaryTreePaths(self, root): 
    if root is None:  
        return [] 
    if (root.left == None and root.right == None): 
        return [str(root.val)] 
    # if left/right is None we'll get empty list anyway 
    return [str(root.val) + '->'+ l for l in  
             self.binaryTreePaths(root.right) + self.binaryTreePaths(root.left)] 

UPD:上面的解决方案使用list comprehensions ，这也是我们如此热爱 Python 的原因之一。这是扩展版本:

def binaryTreePaths(self, root): 
    if root is None:  
        return [] 
    if (root.left == None and root.right == None): 
        return [str(root.val)] 
 
    # subtree is always a list, though it might be empty  
    left_subtree = self.binaryTreePaths(root.left)   
    right_subtree = self.binaryTreePaths(root.right) 
    full_subtree = left_subtree + right_subtree  # the last part of comprehension 
 
    list1 = [] 
    for leaf in full_subtree:  # middle part of the comprehension 
        list1.append(str(root.val) + '->'+ leaf)  # the left part  
 
    return list1