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

Question

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

Answer 1

• 缺少退货声明
• 较低级递归返回列表,而不是单个值(即+=vs. .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:上面的解决方案使用列表推导,这是我们非常喜欢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