在二叉树中查找所有根到叶的路径（在 Python 中）

Question

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

我需要帮助找出我的代码有什么问题 and/or 替代解决方案（最好在 Python 中）。对于我上面给出的示例，我的代码 returns 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

缺少 return 语句
较低级别的递归 returns 列表，而不是单个值（即 += 与 .append()）
列表中的值 return 由较低级别的递归调用编辑，应在前面加上 "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

在二叉树中查找所有根到叶的路径（在 Python 中）

Find all root to leaf paths in a binary tree (in Python)

python

recursion

binary-tree