题目

  输入某二叉树的前序遍历和中序遍历的结果，请重新构造出该二叉树。假设输入的前序遍历和中序遍历的结果中不包含重复的数字。例如输入的前序遍历序列为｛1，2，4，7，3，5，6，8｝和中序遍历为｛4，7，2，1，5，3，6，8｝。则重建出二叉树并输出它的头结点。
  在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树的结点的值位于根节点的值的左边，而右子树的结点的值位于根节点的值的右边。因此我们需要扫描中序遍历序列，才能找到根节点的值。
  如图所示，前序遍历序列的第一个数字1就是根节点的值。扫描中序遍历序列，就能确定根节点的值的位置。根据中序遍历的特点，在根节点的值1前面3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

  由于中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根节点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。

  既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。

代码

/*** 二叉树** @author: xuwenjie01**/
public class BinaryTreeNode {private int value;private BinaryTreeNode left;private BinaryTreeNode right;public BinaryTreeNode(int value) {this.value = value;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public BinaryTreeNode getLeft() {return left;}public void setLeft(BinaryTreeNode left) {this.left = left;}public BinaryTreeNode getRight() {return right;}public void setRight(BinaryTreeNode right) {this.right = right;}
}

/*** @author: xuwenjie01**/
public class ReconstructedBinaryTree {public static void main(String[] args) {ReconstructedBinaryTree solution = new ReconstructedBinaryTree();// 二叉树的先序序列int[] preOrder = {1, 2, 4, 7, 3, 5, 6, 8};// 二叉树的中序序列int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};BinaryTreeNode root = solution.reconstructe(preOrder, inOrder);solution.printPostOrder(root); // 后序打印二叉树}/*** 根据前序和中序遍历序列完成二叉树的重建** @param preOrder 前序遍历序列* @param inOrder  中序遍历序列*/public BinaryTreeNode reconstructe(int[] preOrder, int[] inOrder) {// 入参检查if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0|| preOrder.length != inOrder.length) {return null;}// 二叉树的根节点BinaryTreeNode root = new BinaryTreeNode(preOrder[0]);root.setLeft(null);root.setRight(null);// 左子树的个数int leftNum = 0;for (int i = 0; i < inOrder.length; i++) {if (root.getValue() == inOrder[i]) {break;} else {leftNum++;}}// 右子树的个数int rightNum = inOrder.length - 1 - leftNum;// 重建左子树if (leftNum > 0) {//左子树的先序序列int[] leftPreOrder = new int[leftNum];//左子树的中序序列int[] leftInOrder = new int[leftNum];for (int i = 0; i < leftNum; i++) {leftPreOrder[i] = preOrder[i + 1];leftInOrder[i] = inOrder[i];}BinaryTreeNode leftRoot = reconstructe(leftPreOrder, leftInOrder); // 递归构建左子树root.setLeft(leftRoot);}// 重构右子树if (rightNum > 0) {//右子树的先序序列int[] rightPreOrder = new int[rightNum];//右子树的中序序列int[] rightInOrder = new int[rightNum];for (int i = 0; i < rightNum; i++) {rightPreOrder[i] = preOrder[leftNum + 1 + i];rightInOrder[i] = inOrder[leftNum + 1 + i];}BinaryTreeNode rightRoot = reconstructe(rightPreOrder, rightInOrder); // 递归构建右子树root.setRight(rightRoot);}return root;}/*** 后序遍历二叉树（递归实现）*/public void printPostOrder(BinaryTreeNode root) {if (root != null) {printPostOrder(root.getLeft());printPostOrder(root.getRight());System.out.println(root.getValue());}}}