求指导：将迭代实现的Newick树转二分划分函数改为递归实现

我知道作业类问题可能不受欢迎，但我确实卡壳了。我的任务是把Newick格式的树字符串转换成对应的二分划分，必须用递归方式实现。

示例 #

输入的Newick树：

tree = "((1,2),((3,((4,5),(6,7))),(8,9)))"
read_tree(tree)

对应的二分划分输出：

{{1},{2, 3, 4, 5, 6, 7, 8, 9}}
{{2},{1, 3, 4, 5, 6, 7, 8, 9}}
{{4},{1, 2, 3, 5, 6, 7, 8, 9}}
{{5},{1, 2, 3, 4, 6, 7, 8, 9}}
{{6},{1, 2, 3, 4, 5, 7, 8, 9}}
{{7},{1, 2, 3, 4, 5, 6, 8, 9}}
{{4, 5},{1, 2, 3, 6, 7, 8, 9}}
{{6, 7},{1, 2, 3, 4, 5, 8, 9}}
{{3},{1, 2, 4, 5, 6, 7, 8, 9}}
{{4, 5, 6, 7},{1, 2, 3, 8, 9}}
{{8},{1, 2, 3, 4, 5, 6, 7, 9}}
{{9},{1, 2, 3, 4, 5, 6, 7, 8}}
{{3, 4, 5, 6, 7},{8, 1, 2, 9}}
{{8, 9},{1, 2, 3, 4, 5, 6, 7}}
{{1, 2},{3, 4, 5, 6, 7, 8, 9}}
{{3, 4, 5, 6, 7, 8, 9},{1, 2}}

我的尝试 #

我试过很多思路都失败了，后来想到迭代可以转递归，先写了迭代实现的代码：

def read_tree(newick):
    leaf_set = set()
    index = 0
    for leaf in newick:
        if not leaf == "(" and not leaf == ")" and not leaf == ",":
            leaf_set.add(int(leaf))
    for e in newick:
        if e == ")":
            r_nodes = set()
            l_nodes = set()
            brace_counter = 0
            i_tmp = index-1
            add_ln = False
            add_nodes = True
            while add_nodes:
                if newick[i_tmp] == ")":
                    brace_counter += 1
                if newick[i_tmp] == "(":
                    brace_counter -= 1
                if newick[i_tmp] == "," and brace_counter == 0:
                    add_ln = True
                if not add_ln:
                    if not newick[i_tmp] == "(" 
                    and not newick[i_tmp] == ")" 
                    and not newick[i_tmp] == ",":
                        r_nodes.add(int(newick[i_tmp]))
                if add_ln:
                    if not newick[i_tmp] == "(" 
                    and not newick[i_tmp] == ")" 
                    and not newick[i_tmp] == ",":
                        l_nodes.add(int(newick[i_tmp]))
                if brace_counter == -1 and len(l_nodes) > 0:
                    add_nodes = False
                i_tmp -= 1
            print("{", end="")
            print(l_nodes, end=",")
            print(leaf_set.difference(l_nodes), end="}\n{")
            print(r_nodes, end=",")
            print(leaf_set.difference(r_nodes), end="}\n")
        index += 1

这个迭代版本应该能完成任务，但提交要求必须用递归，我又卡壳了，不知道怎么转成递归形式。不需要完整解决方案，只想要一些思路提示。谢谢！

递归实现思路提示 #

• 抓住Newick的递归本质：每个括号包裹的子树都是独立的子问题，比如(A,B)可以拆成左子树A和右子树B，递归处理这两个子树后再合并结果。
• 明确递归函数的返回值：让递归函数接收一段Newick子串，返回该子树包含的所有叶子节点集合，同时在递归过程中生成对应的二分划分（直接输出或收集起来）。
• 处理终止条件：当子串是单个叶子节点（如"1"），直接返回该节点的集合，无需生成划分。
• 正确拆分左右子树：对于非叶子子串，先去掉外层括号，然后找到括号计数为0时的逗号（即最外层的分隔逗号），将字符串拆分为左右两部分，分别递归处理。
• 生成当前节点的二分划分：拿到左右子树的叶子集合后，用全量叶子集合计算补集，生成{左叶子集合, 补集}和{右叶子集合, 补集}（对应示例中的双向划分）。
• 复用全量叶子集合：提前遍历整个Newick字符串收集所有叶子节点，作为参数传递给递归函数，方便快速计算补集。

内容的提问来源于stack exchange，提问作者Simon