简述Java如何前中序遍历重建二叉树 ？

要使用前序遍历（Pre-order Traversal）和中序遍历（In-order Traversal）的结果来重建二叉树，我们首先需要理解这两种遍历方式的特点：

1. 前序遍历：首先访问根节点，然后访问左子树，最后访问右子树。
2. 中序遍历：首先访问左子树，然后访问根节点，最后访问右子树。

利用这两种遍历方式的特点，我们可以重建二叉树。以下是具体步骤：

1. 从前序遍历中确定根节点

前序遍历的第一个元素总是根节点。

2. 在中序遍历中找到根节点

在中序遍历中，根节点左边的所有元素都位于左子树，右边的所有元素都位于右子树。

3. 递归处理左子树和右子树

• 对于左子树，使用前序遍历中根节点之后的第一个元素作为新的“根节点”，并在中序遍历中找到这个新的“根节点”来分割左子树。
• 对于右子树，使用前序遍历中最后一个元素（在左子树元素之后）作为新的“根节点”，并在中序遍历中找到这个新的“根节点”来分割右子树。

4. 重复上述步骤

递归地对左子树和右子树执行上述步骤，直到所有子树都被重建。

示例

假设我们有以下的前序遍历和中序遍历结果：

• 前序遍历：[1, 2, 4, 5, 3, 6]
• 中序遍历：[4, 2, 5, 1, 6, 3]

我们可以按照以下步骤重建二叉树：

1. 前序遍历的第一个元素 1 是根节点。
2. 在中序遍历中找到 1，其左边的元素是左子树，右边的元素是右子树。
3. 左子树的前序遍历是 [2, 4, 5]，中序遍历是 [4, 2, 5]。
   • 前序遍历的第一个元素 2 是左子树的根节点。
   • 左子树只有一个节点，即 2。
   • 右子树的前序遍历是 [4, 5]，中序遍历是 [4, 5]。
     • 前序遍历的第一个元素 4 是右子树的根节点。
     • 右子树只有一个节点，即 4。
4. 右子树的前序遍历是 [3, 6]，中序遍历是 [6, 3]。
   • 前序遍历的第一个元素 3 是右子树的根节点。
   • 右子树只有一个节点，即 3。

通过上述步骤，我们可以重建原始的二叉树。

注意：这种重建方法假设输入的前序遍历和中序遍历结果是匹配的，并且二叉树中没有重复的元素。如果二叉树中有重复的元素，则需要其他方法或额外的信息来重建二叉树。