题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
思路：前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果
代码实现：
/**
* 题目类型：二叉树
*
* 题目要求：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
*
* 思路：前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，
* 左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果
*/
public class ReConstructBinaryTree {
/**
* 二叉树节点类
*/
private static class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
}
// 缓存中序遍历数组每个值对应的索引
private static Map<Integer, Integer> indexForInOrders = new HashMap<>();
private static TreeNode reconstructBinaryTree(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length || in.length < 1) {
return null;
}
for (int i = 0; i < in.length; i++)
indexForInOrders.put(in[i], i);
return reconstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
/**
* 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树
*
* @param pre 前序遍历数组
* @param preL 前序遍历数组的区间左端点
* @param preR 前序遍历数组的区间右端点
* @param in 中序遍历数组
* @param inL 中序遍历数组的区间左端点
* @param inR 中序遍历数组的区间右端点
*
* @return 新二叉树的根结点
*/
private static TreeNode reconstructBinaryTree(int[] pre, int preL, int preR,int[] in,int inL, int inR) {
// 开始位置大于结束位置说明已经没有需要处理的元素了
if (preL > preR || inL > inR)
return null;
// 新二叉树的根节点为前序遍历数组中的第一个节点
TreeNode root = new TreeNode(pre[preL]);
// 找到中序遍历数组中根节点的索引，将数组分为两部分
int inIndex = indexForInOrders.get(root.value);
// 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常
if (inIndex > inR) {
throw new RuntimeException("Invalid input");
}
// 新二叉树的左子树的节点数
int leftTreeSize = inIndex - inL;
root.left = reconstructBinaryTree(pre, preL + 1, preL + leftTreeSize, in, inL, inL + leftTreeSize - 1);
root.right = reconstructBinaryTree(pre, preL + leftTreeSize + 1, preR, in, inL + leftTreeSize + 1, inR);
return root;
}
/**
* 中序遍历打印二叉树
* @param root
*/
private static void printTree(TreeNode root) {
if (root != null) {
printTree(root.left);
System.out.print(root.value + " ");
printTree(root.right);
}
}
/**
* 测试用例 1：普通二叉树
*/
private static void test1() {
int[] preorder = {1, 2, 4, 7, 3, 5, 6, 8};
int[] inorder = {4, 7, 2, 1, 5, 3, 8, 6};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
/**
* 测试用例 2：完全二叉树
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*/
private static void test2() {
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 5, 1, 6, 3, 7};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
/**
* 测试用例 3 ：所有节点都没有右子节点
*/
private static void test3() {
int[] preorder = {1, 2, 3, 4, 5};
int[] inorder = {5, 4, 3, 2, 1};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
/**
* 测试用例 4：所有节点都没有左子节点
*/
private static void test4() {
int[] preorder = {1, 2, 3, 4, 5};
int[] inorder = {1, 2, 3, 4, 5};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
/**
* 测试用例 5：树中只有一个节点
*/
private static void test5() {
int[] preorder = {1};
int[] inorder = {1};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
/**
* 测试用例 6：二叉树的根节点指针为 null
*/
private static void test6() {
reconstructBinaryTree(null, null);
}
/**
* 测试用例 7:输入的前序遍历序列和中序遍历序列不匹配
*/
private static void test7() {
int[] preorder = {1, 2, 4, 5, 3, 6, 7};
int[] inorder = {4, 2, 8, 1, 6, 3, 7};
TreeNode root = reconstructBinaryTree(preorder, inorder);
printTree(root);
}
public static void main(String[] args) {
System.out.print("测试用例 1：");
test1();
System.out.println();
System.out.print("测试用例 2：");
test2();
System.out.println();
System.out.print("测试用例 3：");
test3();
System.out.println();
System.out.print("测试用例 4：");
test4();
System.out.println();
System.out.print("测试用例 5：");
test5();
System.out.println();
System.out.print("测试用例 6：");
test6();
System.out.println();
//System.out.print("测试用例 7：");
//test7();
}
}
// 输出结果
测试用例 1：4 7 2 1 5 3 8 6
测试用例 2：4 2 5 1 6 3 7
测试用例 3：5 4 3 2 1
测试用例 4：1 2 3 4 5
测试用例 5：1
测试用例 6：
