/**
* 题目：重建二叉树 * 描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 * 解决方案：思路：- 先由前序遍历找到根节点，然后根据根节点和中序遍历，在中序遍历数组中，根节点前面的数字就是左边树的所有节点，根节点后面的数字就是右边树的所有节点。
- 得到新的两个前序遍历序列：前序遍历序列中，根据在中序遍历数组中的得到的根节点下标，可以得到左子树的前序遍历和右子树的前序遍历。
- 得到新的两个中序遍历序列: 中序遍历序列中，根据①中，可以得到所有左边树节点和右边树所有节点，并分别构成新的中序遍历序列
- 递归操作①②③；，分别得到左子树和右子树的根节点，就是①中根节点的左节点和右节点；
* 注：
* 先序遍历：先访问根节点，再左子树，再右子树
* 中序遍历：先访问左子树，再根节点，再右子树 * 后序遍历：先访问左子树，再右子树，再根节点 * */public class One { /** * 根据前序遍历和中序遍历构建二叉树 * @param preOrder 前序遍历 * @param ps 开始位置 * @param pe 结束位置 * @param inOrder 中序遍历序列 * @param is 开始位置 * @param ie 结束位置 * @return 节点 * */ public static BinaryTreeNode construct(int[] preOrder,int ps,int pe,int[] inOrder,int is,int ie) { //如果前序遍历的开始位置大于结束位置，说明已经处理到叶子节点了 if(ps > pe) { return null; } //前序遍历的第一个数字为当前的根节点 int value = preOrder[ps]; //定义一个中间变量 代表中序遍历的开始索引 int index = is; //在中序遍历中寻找根节点的位置，然后分割中序序列，得到新的左边树中序序列和右边树中序序列 while(index ie) { throw new RuntimeException("Error----构建新的根节点"); } BinaryTreeNode node = new BinaryTreeNode(); node.var = value; //前序遍历数组和中序遍历数组中，左子树+根的数量处于数组的前面位置 //比如 前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} ，前四个数字1、2、4、7就是左子树和根，只是顺序不一样。 //所以 preOrder中，需要从ps+1位置开始，ps+index-is结束。 node.left = construct(preOrder, ps+1,ps+index-is, inOrder, is, index-1); node.right = construct(preOrder, ps+index-is+1, pe, inOrder, index+1, ie); return node; } static class BinaryTreeNode{ int var; BinaryTreeNode left; BinaryTreeNode right; }}