如何基于字符串表达式构建二叉树 中序遍历实现方案问询

首先先明确该类字符串的通用编码规则：( 代表子树起始，) 代表子树结束，! 是节点值的起止分隔符，两个!中间的内容为节点值，无!标记的括号范围对应空节点，整体字符串顺序严格对应二叉树中序遍历的「左子树-根节点-右子树」顺序。 #

核心实现思路 #

• 选择栈作为核心数据结构处理括号的嵌套层级关系，天然适配嵌套子树的解析场景
• 逐字符遍历字符串，同步维护当前处理节点与栈内层级关系：

  遇到(时往栈内压入空占位符，标记新一层子树开始
  遇到!时读取两个!之间的内容生成真实二叉树节点，替换栈顶的空占位符
  遇到)时弹出栈顶的当前子树根节点，将其挂载到上层父节点的空缺子节点位置：上层父节点左子节点为空则挂载到左，左子节点已存在则挂载到右

• 遍历完成后，栈底剩余的唯一节点即为整棵二叉树的根节点

可参考的实现技巧 #

• 提前做输入预处理：如果输入存在冗余空格可以提前统一移除，减少遍历过程中的无效判断分支，无空格输入可跳过该步骤
• 用指针偏移提升遍历效率：遇到!后直接查找下一个配对!的索引，一次性读取完整节点值，不需要逐字符拼接，比如Python中可以用str.find('!', current_pos)快速定位分隔符位置
• 栈内存储二元组简化逻辑：可以将栈元素定义为(父节点, 子节点挂载标记)，提前约定下一个弹出节点的挂载位置，不用额外判断父节点左右子节点的占用状态
• 增加边界校验逻辑：提前校验括号配对数量、!配对数量，避免非法输入导致的数组越界、逻辑混乱问题

参考代码片段（Python） #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(s: str) -> TreeNode:
    stack = []
    n = len(s)
    i = 0
    while i < n:
        if s[i] == '(':
            stack.append(None)
            i += 1
        elif s[i] == ')':
            cur_node = stack.pop()
            if stack:
                parent_node = stack[-1]
                if parent_node.left is None:
                    parent_node.left = cur_node
                else:
                    parent_node.right = cur_node
            i += 1
        elif s[i] == '!':
            i += 1
            val_start_idx = i
            # 直接找下一个!的位置，读取节点值
            while i < n and s[i] != '!':
                i += 1
            node_val = s[val_start_idx:i]
            stack.append(TreeNode(node_val))
            i += 1
        else:
            # 跳过无意义的特殊字符
            i += 1
    return stack[0] if stack else None

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