根据字符串输入创建二叉树

Question

我正在尝试创建一个递归（或循环）函数，该函数以字符串为输入，形成"（2（1）（3））"（我不担心对其进行排序），并将其解释为一个列表，将其转换为一个二进制树，如[2[1[][]][3[][]]]。这是我到目前为止所做的，但没有效果。到目前为止，我得到的是：

def subtrees(string):
    tree = []
    for x in string:
        if x == "(":
            return tree.append(subtrees(string[1:]))
        elif x == ")":
            return tree
        else:
            tree.append(int(x))
            return tree.append(subtrees(string[1:]))

经过广泛的测试，我发现了两个大错误：一个是return在找到第一个闭括号后完成了整个正在运行的函数（而不仅仅是一个结束节点的递归调用），另一个原因是，当我尝试打印输出时，它会打印None。任何帮助/提示都将不胜感激，因为我在这里真的很失落。

Answer 1

您的函数存在许多问题：

• list.append（）返回None
• 每种情况都会返回（由于以上原因，通常为"无"）
• 你的元素不必要地重复出现
• 递归函数不会推进外部函数，因为您正在传递字符串的副本，请将字符串转换为可迭代的

快速修复：

def subtrees(string):
    s = iter(string)
    tree = []
    for x in s:
        if x == "(":
            tree.append(subtrees(s))
        elif x == ")":
            return tree
        else:
            tree.append(int(x))
    return tree[0]
>>> subtrees('(2(1)(3))')
[2, [1], [3]]