根据InOrder格式字符串构建BinaryTree的实现问题咨询

原代码问题分析 #

你现有代码的核心问题是没有按照给定格式拆分左子树、根节点、右子树的边界：

• 未识别非空树外层包裹的()结构，也没有定位根节点的位置
• 递归时直接将剩余整段字符串传给左右子树的构建逻辑，参数范围完全错误，自然无法正确生成树结构。

核心实现思路 #

给定的非空树格式固定为(左子树根节点右子树)，我们可以利用括号匹配规则拆分结构：

1. 遇到!直接返回空树
2. 非空树首先去掉首尾的()，得到内容串左子树串 + 根字符 + 右子树串
3. 用括号计数法匹配左子树的结束位置：如果左子树是!则长度为1；如果是嵌套结构，计数到左右括号数量相等时就是左子树的结束位置
4. 左子树结束位置的下一个字符就是根节点，根节点之后的内容就是右子树串
5. 递归构建左右子树后拼接当前节点返回

完整修正代码 #

构造器调整 #

public BinaryTree(String tree) {
    // 空树直接赋值root为null
    if (tree == null || tree.isEmpty() || tree.charAt(0) == '!') {
        root = null;
        return;
    }
    root = buildTree(tree).root;
}

递归方法与辅助工具 #

private BinaryTree buildTree(String tree) {
    // 空树直接返回空实例
    if (tree.charAt(0) == '!') {
        return new BinaryTree();
    }
    // 去掉非空树外层的()
    String content = tree.substring(1, tree.length() - 1);
    // 查找左子树结束下标
    int leftEndIdx = findLeftSubtreeEnd(content);
    // 拆分三部分
    String leftSubtreeStr = content.substring(0, leftEndIdx + 1);
    char rootVal = content.charAt(leftEndIdx + 1);
    String rightSubtreeStr = content.substring(leftEndIdx + 2);
    // 递归构建左右子树
    BinaryTree left = buildTree(leftSubtreeStr);
    BinaryTree right = buildTree(rightSubtreeStr);
    // 返回当前树实例
    return new BinaryTree(left, rootVal, right);
}

// 辅助方法：返回左子树在内容串中的最后一个下标
private int findLeftSubtreeEnd(String content) {
    // 左子树是空的情况，!占第一个位置
    if (content.charAt(0) == '!') {
        return 0;
    }
    // 嵌套结构括号匹配计数
    int bracketCount = 0;
    for (int i = 0; i < content.length(); i++) {
        char c = content.charAt(i);
        if (c == '(') bracketCount++;
        else if (c == ')') bracketCount--;
        // 计数归0说明左子树括号完全匹配，到达结束位置
        if (bracketCount == 0) {
            return i;
        }
    }
    throw new IllegalArgumentException("输入的树格式不合法");
}

使用说明 #

• 代码默认你提供的BinaryTree无参构造会生成空树（root为null），三参数构造的参数顺序为「左子树实例、根节点值、右子树实例」，如果你的构造定义不同可自行调整参数顺序
• 输入字符串需要保证格式合法、括号完全匹配，否则会抛出异常

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