解析字符串构建二叉树遇问题，求解决方案与思路提示

我需要解析类似"27(3(4,5),2(,))"格式的字符串构建二叉树：其中27是根节点key，3是左子节点，2是右子节点。计划通过逗号分割后递归调用函数构建子树，忽略负数，不存在的子树设为None。

目前思路方向正确，但代码处理右子树时存在问题，尝试过用括号替换逗号简化处理仍未解决。以下是我的原Python代码及测试用例，求解决方法或思路提示：

原代码 #

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def createTree(string):
    if string is None or string == "":
        return None

    # 解析节点key（支持多位数）
    key = 0
    i = 0
    while i < len(string) and string[i] != "(":
        key = key * 10 + int(string[i])
        i += 1

    # 创建当前节点
    node = Node(key)

    # 叶子节点直接返回
    if i == len(string):
        return node

    # 寻找分隔左右子树的逗号位置
    leftStart = i
    leftParenthesesCount = 0
    for j in range(i, len(string)):
        if string[j] == "(":
            leftParenthesesCount += 1
        elif string[j] == ")":
            leftParenthesesCount -= 1
        elif string[j] == "," and leftParenthesesCount == 1:
            break

    # 寻找左子树的闭合括号位置
    leftEnd = j
    leftParenthesesCount = 1
    for j in range(j + 1, len(string)):
        if string[j] == "(":
            leftParenthesesCount += 1
        elif string[j] == ")":
            leftParenthesesCount -= 1
            if leftParenthesesCount == 0:
                break

    # 寻找右子树的闭合括号位置
    rightEnd = len(string) - 1
    rightParenthesesCount = 1
    for j in range(len(string) - 2, -1, -1):
        if string[j] == ")":
            rightParenthesesCount += 1
        elif string[j] == "(":
            rightParenthesesCount -= 1
            if rightParenthesesCount == 0:
                break

    # 递归构建左右子树
    if leftStart + 1 < leftEnd:
        node.left = createTree(string[leftStart + 1:leftEnd])
    if leftEnd + 2 < rightEnd:
        node.right = createTree(string[leftEnd + 2:rightEnd])

    return node

测试用例 #

str = "35(22(7,2),5(4,))"
str2 = "27(2,)" 
str3 = "6(5,4)" 
str4 = "3(2,)" 
str5 = "1(,52)" 
str6 = "567(,35(16(89(,22(55(55(92,12),12(1(,12(14,15(16,17(,92(,92))))),92(92,))),16(,1(1(,13(,77)),)))),),35(35,)))"

问题分析与修复方案 #

你的原代码核心问题在于右子树的索引计算逻辑冗余且错误，没必要从后往前遍历寻找右子树边界——因为整个字符串的结构是根节点(左子树,右子树)，右子树的范围必然是从分隔逗号的下一位，到整个字符串的倒数第二个字符（排除末尾的)）。同时左子树的边界计算也可以简化，以下是修复后的代码：

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def createTree(string):
    if not string:
        return None

    # 解析多位数key，忽略负数
    key = 0
    i = 0
    while i < len(string) and string[i] != "(":
        if string[i] == '-':
            i += 1
            continue
        key = key * 10 + int(string[i])
        i += 1

    # 创建当前节点
    node = Node(key)

    # 叶子节点直接返回
    if i == len(string):
        return node

    # 找到分隔左右子树的逗号（匹配括号层级）
    comma_idx = -1
    parenthesis_count = 1  # 从根节点的'('开始计数
    for j in range(i + 1, len(string)):
        if string[j] == '(':
            parenthesis_count += 1
        elif string[j] == ')':
            parenthesis_count -= 1
            if parenthesis_count == 0:
                break
        elif string[j] == ',' and parenthesis_count == 1:
            comma_idx = j
            break

    # 处理左子树：从'('后到逗号前（有内容才递归）
    if comma_idx != -1 and i + 1 < comma_idx:
        node.left = createTree(string[i+1:comma_idx])
    else:
        node.left = None

    # 处理右子树：从逗号后到末尾')'前（有内容才递归）
    if comma_idx != -1 and comma_idx + 1 < len(string) - 1:
        node.right = createTree(string[comma_idx+1:-1])
    else:
        node.right = None

    return node

关键修改点： #

1. 简化边界计算：右子树直接取逗号后到字符串倒数第二位的子串，无需额外遍历括号。
2. 完善括号层级判断：只有当括号层级为1（当前节点的括号范围内）时，逗号才是左右子树的分隔符，避免误判嵌套结构中的逗号。
3. 增加负数忽略逻辑：遇到'-'直接跳过，不解析负数key。
4. 明确空值处理：当子树位置无有效内容时，直接设为None，比如"27(2,)"的右子树、"1(,52)"的左子树都会被正确设置为None。

你可以用测试用例验证，比如str5 = "1(,52)"会生成根节点1，左子树为None、右子树为52的节点；str2 = "27(2,)"会生成根节点27，左子树为2、右子树为None的结构。

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