7.重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历都不含重复的数字。例如输入前序遍历序列{1，2，4，7，3，5，6，8}和中序遍历序列{4，7，2，1，5，3，8，6}，重建其二叉树并返回其根节点。
首先说明一下二叉树的前序遍历：前序遍历序列中，第一个数字总是根节点的值。
中序遍历：根节点的值在序列的中间，左子树的节点位于根节点的值的左边，而右子树的值位于根节点的值的右边。
根据上述思想我们可以得出以下结论：
1.前序遍历的第一个数字是1，说明了根节点是1。
2.中序遍历中，已知根节点为1，那么根节点1的左边是左子树，1的右边是右子树。![]()
很明显，我们可以使用递归法解题。时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)。
classsolution1{publicTreeNodereConstructBinaryTree(int[]pre,int[]in){if(pre==null||in==null||pre.length==0||in.length==0){returnnull;}if(pre.length!=in.length){returnnull;}TreeNoderoot=newTreeNode(pre[0]);for(inti=0;i<pre.length;i++){if(pre[0]==in[i]){root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));}}returnroot;}}
