1、问题：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
2、分析：
（1）根据当前的前序遍历和中序遍历确定头结点，并且将数组分割成左孩子集合和右孩子集合。
（2）根据1的规则进行递归处理。
（3）结束条件：数组长度为0，返回null；数组长度为2，进行判断——》两个数组的第一个元素相等，则第二个元素为右孩子节点，否则为左孩子节点。
3、代码参考：
1 import java.util.Arrays; 2 public class Solution { 3 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 4 if(pre==null || pre.length==0) { 5 return null; 6 } 7 TreeNode head = new TreeNode(pre[0]); 8 if(pre.length==2) { 9 TreeNode node = new TreeNode(pre[1]); 10 if(pre[1]!=in[1]) { 11 12 head.left = node; 13 }else { 14 head.right = node; 15 } 16 return head; 17 } 18 19 int i= 0; 20 for(;i<in.length;i++) { 21 if(in[i]==pre[0]) break; 22 } 23 head.left = i==0?null:reConstructBinaryTree(Arrays.copyOfRange(pre, 1,i+1),Arrays.copyOfRange(in, 0, i)); 24 head.right= i==pre.length-1?null:reConstructBinaryTree(Arrays.copyOfRange(pre, i+1,pre.length),Arrays.copyOfRange(in, i+1, in.length)); 25 26 return head; 27 } 28 }
原文：https://www.cnblogs.com/dream-flying/p/12885596.html