java语言数据结构

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以根据给定的前序遍历序列（ABECDFGHIJ）和中序遍历序列（EBCDAFHIGJ），通过逆向思维构建一棵二叉树。

1. 前序遍历：从左到右依次访问根节点、左子节点、右子节点。
2. 中序遍历：先访问左子节点，然后访问根节点，最后访问右子节点。

首先，我们可以通过这两个顺序得到两个不同的节点数组，一个用于前序遍历，另一个用于中序遍历。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) { val = x; }
}

public void createTree(String[] preOrder, String[] inOrder) {
    // 将字符串转换为整数数组
    int[] preorderArray = new int[preOrder.length];
    for (int i = 0; i < preOrder.length; i++) {
        preorderArray[i] = Integer.parseInt(preOrder.charAt(i));
    }

    int[] inorderArray = new int[inOrder.length];
    for (int i = 0; i < inOrder.length; i++) {
        inorderArray[i] = Integer.parseInt(inOrder.charAt(i));
    }

    // 前序遍历
    createPreorder(preorderArray, 0, preorderArray.length - 1);

    // 中序遍历
    createInorder(inorderArray, 0, inorderArray.length - 1);
}

接下来，我们将递归地创建每个节点，并在每个节点上添加相应的左右子节点。

void createPreorder(int[] preorderArray, int start, int end) {
    if (start > end) return; // 如果开始索引大于结束索引，则退出函数

    // 获取当前节点值
    int rootValue = preorderArray[start];

    // 创建新节点
    TreeNode node = new TreeNode(rootValue);

    // 根据根节点值找到左子节点索引
    int leftChildIndex = findLeftChildIndex(start + 1, end, rootValue);

    // 左子节点存在时，递归创建左子节点
    if (leftChildIndex != -1) {
        createPreorder(preorderArray, start + 1, leftChildIndex - 1);
        node.left = preorderArray[leftChildIndex]; // 设置左子节点
    }

    // 右子节点存在时，递归创建右子节点
    if (leftChildIndex + 1 != end) {
        createPreorder(preorderArray, leftChildIndex + 1, end); // 递归调用
        node.right = preorderArray[leftChildIndex + 1]; // 设置右子节点
    }
}

// 寻找左子节点索引
private int findLeftChildIndex(int startIndex, int endIndex, int value) {
    while (startIndex <= endIndex) {
        int mid = startIndex + (endIndex - startIndex) / 2; // 求中间索引
        if (value == preorderArray[mid]) {
            return mid; // 找到了左子节点，返回索引
        } else if (value < preorderArray[mid]) {
            endIndex = mid - 1; // 右子节点可能存在，缩小搜索范围
        } else {
            startIndex = mid + 1; // 左子节点可能存在，缩小搜索范围
        }
    }
    return -1; // 未找到左子节点，返回-1
}

void createInorder(int[] inorderArray, int start, int end) {
    if (start > end) return; // 如果开始索引大于结束索引，则退出函数

    // 获取当前节点值
    int rootValue = inorderArray[start];

    // 创建新节点
    TreeNode node = new TreeNode(rootValue);

    // 根据根节点值找到左子节点索引
    int leftChildIndex = findLeftChildIndex(start + 1, end, rootValue);

    // 左子节点存在时，递归创建左子节点
    if (leftChildIndex != -1) {
        createInorder(inorderArray, start + 1, leftChildIndex - 1);
        node.left = inorderArray[leftChildIndex]; // 设置左子节点
    }

    // 右子节点存在时，递归创建右子节点
    if (leftChildIndex + 1 != end) {
        createInorder(inorderArray, leftChildIndex + 1, end); // 递归调用
        node.right = inorderArray[leftChildIndex + 1]; // 设置右子节点
    }
}

// 寻找左子节点索引
private int findLeftChildIndex(int startIndex, int endIndex, int value) {
    while (startIndex <= endIndex) {
        int mid = startIndex + (endIndex - startIndex) / 2; // 求中间索引
        if (value == inorderArray[mid]) {
            return mid; // 找到了左子节点，返回索引
        } else if (value < inorderArray[mid]) {
            endIndex = mid - 1; // 右子节点可能存在，缩小搜索范围
        } else {
            startIndex = mid + 1; // 左子节点可能存在，缩小搜索范围
        }
    }
    return -1; // 未找到左子节点，返回-1
}

以上代码将分别计算并创建前序遍历和中序遍历的每个节点，从而构建一棵二叉树。注意，在实际应用中，可能还需要考虑一些额外的逻辑，比如处理特殊情况下（例如重复元素）。