从字符串输入创建二叉树

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。任何 help/hints 都将不胜感激，因为我在这里真的很迷路。

Answer 1

你的函数有很多问题：

list.append() returns None
你为每个条件返回（通常 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]]

从字符串输入创建二叉树

Creating a Binary Tree from string input

python

binary-tree

python-3.x